剑指 Offer | 03. 数组中重复的数字

剑指 Offer 03. 数组中重复的数字 - 力扣（LeetCode）https://leetcode.cn/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/今天开个坑，刷一波剑指offer（虽然零散刷过一点。。。

法一：利用HashSet可以快速查找的特点，将元素放入HashSet中并比较。

class Solution {
    public int findRepeatNumber(int[] nums) {
        HashSet<Integer> integers = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (integers.contains(nums[i])) {
                return nums[i];
            }
            integers.add(nums[i]);
        }
        return -1;
    }
}

法二：下标法， 不断交换元素，使元素与其对应下标 相同，直至发生冲突。

class Solution {
    public int findRepeatNumber(int[] nums) {
        // 遍历数组
        for(int i = 0; i < nums.length; i++) {
            // 之所以用while，是因为交换之后，该位置的元素任然没有在正确的位置
            while(i != nums[i]){
                if(nums[i] == nums[nums[i]]){
                    return nums[i];
                }
                // nums[i] 正确的位置在 nums[nums[i]]
                int k = nums[nums[i]];
                nums[nums[i]] = nums[i];
                nums[i] = k;
            }
        }
        return -1;
    }
}