# 查找重複的號碼

## 範例檔案

nums = {1、3、4、2、2}

2

nums = {3、1、3、4、2}

3

## 查找重複編號的幼稚方法

### 方法1（蠻力）

#### JAVA代碼

```public class FindTheDuplicateElement {
private static int findDuplicate(int nums[]) {
int n = nums.length;

for (int i = 0; i < n; i++) {
// For every element check if it is repeated in the elements ahead of it
for (int j = i + 1; j < n; j++) {
// If repeated, this is the duplicate element
if (nums[j] == nums[i])
return nums[i];
}
}
// No duplicate found
return -1;
}

public static void main(String[] args) {
// Example 1
int nums[] = new int[]{1, 3, 4, 2, 2};
System.out.println(findDuplicate(nums));

// Example 2
nums = new int[]{3, 1, 3, 4, 2};
System.out.println(findDuplicate(nums));
}
}```

#### C ++代碼

```#include <bits/stdc++.h>
using namespace std;

int findDuplicate(int *nums, int n) {
for (int i = 0; i < n; i++) {
// For every element check if it is repeated in the elements ahead of it
for (int j = i + 1; j < n; j++) {
// If repeated, this is the duplicate element
if (nums[i] == nums[j])
return nums[i];
}
}
// Duplicate not found
return -1;
}

int main() {
// Example 1
int nums[] = {1, 3, 4, 2, 2};
int n = sizeof(nums) / sizeof(nums[0]);
cout<<findDuplicate(nums, n)<<endl;

// Example 2
int nums2[] = {3, 1, 3, 4, 2};
n = sizeof(nums2) / sizeof(nums2[0]);
cout<<findDuplicate(nums2, n);

return 0;
}```
```2
3```

### 方法2（排序）

#### JAVA代碼

```import java. util. Arrays;
public class FindTheDuplicateElement {
private static int findDuplicate(int[] nums) {
int n = nums.length;
// Sort the array
Arrays.sort(nums);
// Check the adjacent elements
for (int i = 0; i < n - 1; i++) {
// If adjacent elements are equal, this is the duplicate element
if (nums[i] == nums[i + 1])
return nums[i];
}
// No duplicate found
return -1;
}

public static void main(String[] args) {
// Example 1
int nums[] = new int[]{1, 3, 4, 2, 2};
System.out.println(findDuplicate(nums));

// Example 2
nums = new int[]{3, 1, 3, 4, 2};
System.out.println(findDuplicate(nums));
}
}```

#### C ++代碼

```#include <bits/stdc++.h>
using namespace std;

int findDuplicate(int *nums, int n) {
// Sort the array
sort(nums, nums + n);
// Check the adjacent elements
for (int i = 0; i < n - 1; i++) {
// If adjacent elements are equal, this is the duplicate element
if (nums[i] == nums[i + 1])
return nums[i];
}
// Duplicate not found
return -1;
}

int main() {
// Example 1
int nums[] = {1, 3, 4, 2, 2};
int n = sizeof(nums) / sizeof(nums[0]);
cout<<findDuplicate(nums, n)<<endl;

// Example 2
int nums2[] = {3, 1, 3, 4, 2};
n = sizeof(nums2) / sizeof(nums2[0]);
cout<<findDuplicate(nums2, n);

return 0;
}```
```2
3```

## 查找重複編號的最佳方法

### 方法1（散列）

#### 用於查找重複編號的JAVA代碼

```import java.util.*;
public class FindTheDuplicateElement {
private static int findDuplicate(int[] nums) {
int n = nums.length;
// Create a HashSet
HashSet<Integer> set = new HashSet<>();
for (int i = 0; i < n; i++) {
// If the HashSet contains the element, then this is the duplicate
if (set.contains(nums[i]))
return nums[i];
// Else add the element to the set
set.add(nums[i]);
}
// No duplicate found
return -1;
}

public static void main(String[] args) {
// Example 1
int nums[] = new int[]{1, 3, 4, 1, 2, 5};
System.out.println(findDuplicate(nums));

// Example 2
nums = new int[]{3, 1, 4, 2, 5, 5};
System.out.println(findDuplicate(nums));
}
}```

#### 查找重複編號的C ++代碼

```#include <bits/stdc++.h>
using namespace std;

int findDuplicate(int *nums, int n) {
// Create a HashSet
unordered_set<int> set;
for (int i = 0; i < n; i++) {
// If the HashSet contains the element, then this is the duplicate
if (set.find(nums[i]) != set.end())
return nums[i];
// Else add the element to the set
set.insert(nums[i]);
}
// Duplicate not found
return -1;
}

int main() {
// Example 1
int nums[] = {1, 3, 4, 1, 2, 5};
int n = sizeof(nums) / sizeof(nums[0]);
cout<<findDuplicate(nums, n)<<endl;

// Example 2
int nums2[] = {3, 1, 5, 4, 2, 5};
n = sizeof(nums2) / sizeof(nums2[0]);
cout<<findDuplicate(nums2, n);

return 0;
}```
```1
5```

### 方法2（XOR）

1. 初始化一個整數X作為元素從1到n的XOR，其中nums數組的大小為（n + 1）。
2. 將另一個整數Y初始化為0。
3. 遍歷數組並將Y更新為（Y ^ nums [i]），即Y存儲nums數組的所有元素的XOR。
4. 重複元素是（X ^ Y）。

#### 用於查找重複編號的JAVA代碼

```public class FindTheDuplicateElement {
private static int findDuplicate(int[] nums) {
int n = nums.length;
// Initialise X as XOR of elements from 1 to n
// Size of nums is (n + 1), here represented as n
int X = 0;
for (int i = 1; i <= n - 1; i++)
X = (X ^ i);

// Initialise Y as 0 and update Y = Y ^ nums[i] at every iteration
int Y = 0;
for (int i = 0; i < n; i++) {
Y = Y ^ nums[i];
}

// Duplicate element is (X ^ Y)
return (X ^ Y);
}

public static void main(String[] args) {
// Example 1
int nums[] = new int[]{1, 3, 4, 2, 4};
System.out.println(findDuplicate(nums));

// Example 2
nums = new int[]{3, 1, 3, 4, 2};
System.out.println(findDuplicate(nums));
}
}```

#### 查找重複編號的C ++代碼

```#include <bits/stdc++.h>
using namespace std;

int findDuplicate(int *nums, int n) {
// Initialise X as XOR of elements from 1 to n
// Size of nums is (n + 1), here represented as n
int X = 0;
for (int i = 1; i <= n - 1; i++)
X = X ^ i;

// Initialise Y as 0 and update Y = Y ^ nums[i] at every iteration
int Y = 0;
for (int i = 0; i < n; i++)
Y = Y ^ nums[i];

// Duplicate element is (X ^ Y)
return (X ^ Y);
}

int main() {
// Example 1
int nums[] = {1, 3, 4, 2, 4};
int n = sizeof(nums) / sizeof(nums[0]);
cout<<findDuplicate(nums, n)<<endl;

// Example 2
int nums2[] = {3, 1, 3, 4, 2};
n = sizeof(nums2) / sizeof(nums2[0]);
cout<<findDuplicate(nums2, n);

return 0;
}```
```4
3```

### 方法3（週期檢測）

nums [] = {1、3、4、2、2}

1. 初始化兩個指針，慢速和快速初始化為nums [0]。
2. 當slow和fast不相等時，請執行slow = nums [slow]和fast = nums [nums [fast]]。
3. 在第2步之後，將lower分配為nums [0]，並分別將慢速指針和快速指針移動一步，即，
slow = nums [slow]
fast = nums [快速]
而慢和快並不相等。
4. 步驟3之後，慢速和快速都指向重複元素。

#### 用於查找重複編號的JAVA代碼

```public class FindTheDuplicateElement {
private static int findDuplicate(int[] nums) {
int n = nums.length;
//Initialize two pointers slow and fast as nums[0].
int slow = nums[0], fast = nums[0];
// Do slow = nums[slow] and fast = nums[nums[fast]]
// while slow and fast are not equal.
do {
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow != fast);

// assign slow as nums[0]
slow = nums[0];
// Move slow and fast by one step each while slow and fast are not equal
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}

// Both slow and fast points to the duplicate element
return fast;
}

public static void main(String[] args) {
// Example 1
int nums[] = new int[]{1, 3, 4, 4, 2};
System.out.println(findDuplicate(nums));

// Example 2
nums = new int[]{3, 1, 5, 4, 2, 5};
System.out.println(findDuplicate(nums));
}
}```

#### 查找重複編號的C ++代碼

```#include <bits/stdc++.h>
using namespace std;

int findDuplicate(int *nums, int n) {
//Initialize two pointers slow and fast as nums[0].
int slow = nums[0], fast = nums[0];
// Do slow = nums[slow] and fast = nums[nums[fast]]
// while slow and fast are not equal.
do {
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow != fast);

// assign slow as nums[0]
slow = nums[0];
// Move slow and fast by one step each while slow and fast are not equal
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}

// Both slow and fast points to the duplicate element
return fast;
}

int main() {
// Example 1
int nums[] = {1, 3, 4, 4, 2};
int n = sizeof(nums) / sizeof(nums[0]);
cout<<findDuplicate(nums, n)<<endl;

// Example 2
int nums2[] = {3, 1, 5, 4, 2, 5};
n = sizeof(nums2) / sizeof(nums2[0]);
cout<<findDuplicate(nums2, n);

return 0;
}```
```4
5```