First duplicate value

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.

class Program {

  public int firstDuplicateValue(int[] array) {
        int n = array.length;
        int min_index = n; // initialze the min_index as the length of array.
        
        for(int i = 0; i < n; i++){
            int value_a = array[i];
            for(int j = i+1; j < n; j++){
                int value_b = array[j];
                if(value_a == value_b){
                    min_index = Math.min(min_index, j);//update the min_index
                }
            }
        }        
        if(min_index == n){//no duplicate values in the array
            return -1;
        }
        return array[min_index];//return the value, not just the index!!!
  }
}

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

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

HashSet： 不允许重重元素

HashMap: 允许重复元素

class Program {

  public int firstDuplicateValue(int[] array) {
    HashSet<Integer> set = new HashSet<Integer>();
        
        for(int value: array){
            if(set.contains(value)){
                return value;
            }else{
                set.add(value);
            }
        }
        return -1;
  }
}

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].

class Program {

  public int firstDuplicateValue(int[] array) {
    // Write your code here.
        for(int value: array){
            int absValue = Math.abs(value);//update the index.
            if(array[absValue-1]<0) return absValue;
            array[absValue-1] *= -1;
        }
    return -1;
  }
}