数组中重复的数字

在一个长度为 n 的数组里，所有数字都在 0 到 n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复，也不知道每个数字重复几次。请找出数组中第一个重复的数字。例如，如果输入长度为 7 的数组 {2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字 2

解法一

利用 HashMap 键不重复的特性，可以轻松找出第一个重复的数字

/*
 * 返回描述：
 * 如果数组中有重复的数字，函数返回true，否则返回false
 * 如果数组中有重复的数字，把重复的数字放到参数duplication[0]中
 */
import java.util.HashMap;
public class Solution {
    public boolean duplicate(int numbers[],int length,int [] duplication) {
        boolean flag = false;
        HashMap<Integer, Object> map = new HashMap<>();
        for(int i = 0; i < length; i++) {
            if(map.containsKey(numbers[i])) {
                duplication[0] = numbers[i];
                flag = true;
                break;
            }
            map.put(numbers[i], null);
        }
        return flag;
    }
}

解法二

有一个条件我们没有用到，就是数据的范围是 0 ~ n-1，所以我们可以这么做：

• 设置一个指针 i 指向开头 0
• 对于 arr[i] 进行判断，如果 arr[i] == i，说明下标为 i 的数据正确的放在了该位置上，让 i++
• 如果 arr[i] != i，说明没有正确放在位置上，那么我们就把 arr[i] 放在正确的位置上，也就是交换 arr[i] 和 arr[arr[i]]。交换之后，如果 arr[i] ！= i，继续交换
• 如果交换的过程中，arr[i] == arr[arr[i]]，说明遇到了重复值，返回即可

/*
 * 返回描述：
 * 如果数组中有重复的数字，函数返回true，否则返回false
 * 如果数组中有重复的数字，把重复的数字放到参数duplication[0]中
 */
public class Solution {
    public boolean duplicate(int numbers[],int length,int [] duplication) {
        for(int i = 0; i < length; i++) {
            // 不相等就一直交换
            if(i != numbers[i]) {
                if(numbers[i] != numbers[numbers[i]]) {
                    int temp = numbers[numbers[i]];
                    numbers[numbers[i]] = numbers[i];
                    numbers[i] = temp;
                } else {
                    duplication[0] = numbers[i];
                    return true;
                }
            }
        }
        return false;
    }
}

解法三

还是之前的条件，数据的范围是 0 ~ n-1，所以可以利用现有数组设置标志，当一个数字被访问过后，可以设置对应位上的数 + n，之后再遇到相同的数时，会发现对应位上的数已经大于等于n了，那么直接返回这个数即可

/*
 * 返回描述：
 * 如果数组中有重复的数字，函数返回true，否则返回false
 * 如果数组中有重复的数字，把重复的数字放到参数duplication[0]中
 */
public class Solution {
    public boolean duplicate(int numbers[],int length,int [] duplication) {
        if(numbers == null || numbers.length == 0) {
            duplication[0] = -1;
            return false;
        }
        for(int i = 0; i < numbers.length; i++) {
        	// 得到当前正在遍历的数
            int index = numbers[i];
            // index 有可能已被改变，为了找到正确的对应数组位置，必须减去length 
            if(index >= length) {
                index -= length;
            }
            // 对应位置如果大于length，则为重复数字
            if(numbers[index] >= length) {
                duplication[0] = index;
                return true;
            }
            numbers[index] += length;
        }
        return false;
    }
}