From : https://www.algoexpert.io/questions/First%20Duplicate%20Value

---

 

First duplicate value

1. problem statement

给定一个长度为n的数组，这个数组包含的整数的范围在[1,n]，我们需要找到第一个有重复的整数，如果数组包含多个重复的数字，则返回索引号最小的那个数字；如果没有重复的，返回-1.

2. brute force. (O(n^2), O(1))贪心算法。

遍历整个数组，对于数组里的每一个元素，遍历内层for loop在[i+1,n]中寻找它的重复元素，一旦array[I] == array[j]，更新min_index，遍历结束之后返回min_index所对应的元素值。

initialize the min_index as array.length, if min_index = array.length, return -1.

 1 class Program {
 2 
 3   public int firstDuplicateValue(int[] array) {
 4         int n = array.length;
 5         int min_index = n; // initialze the min_index as the length of array.
 6         
 7         for(int i = 0; i < n; i++){
 8             int value_a = array[i];
 9             for(int j = i+1; j < n; j++){
10                 int value_b = array[j];
11                 if(value_a == value_b){
12                     min_index = Math.min(min_index, j);//update the min_index
13                 }
14             }
15         }        
16         if(min_index == n){//no duplicate values in the array
17             return -1;
18         }
19         return array[min_index];//return the value, not just the index!!!
20   }
21 }

3. Hash map(O(n), O(n))

用哈希表存储unique values，然后检查重复元素，一旦找到了直接返回。（找到的第一个重复元素即为所求）

HashSet： 不允许重重元素

HashMap: 允许重复元素

 1 class Program {
 2 
 3   public int firstDuplicateValue(int[] array) {
 4     HashSet<Integer> set = new HashSet<Integer>();
 5         
 6         for(int value: array){
 7             if(set.contains(value)){
 8                 return value;
 9             }else{
10                 set.add(value);
11             }
12         }
13         return -1;
14   }
15 }

4. index mapping （O(n), O(1)）

充分利用数组里面所存的元素的值属于[1,n]， map the values by their indexes.

index = value-1

same value==same index, set array[value - 1] *= -1

if array[value - 1] < 0, return value

why value-1?, range of values:[1,n], value-1: [0,n-1], index is in [0,n-1].

 1 class Program {
 2 
 3   public int firstDuplicateValue(int[] array) {
 4     // Write your code here.
 5         for(int value: array){
 6             int absValue = Math.abs(value);//update the index.
 7             if(array[absValue-1]<0) return absValue;
 8             array[absValue-1] *= -1;
 9         }
10     return -1;
11   }
12 }