2021.10.08 - JZ03.数组中重复的数字

• 1. 题目
• 2. 思路
• • (1) HashSet
  • (2) 原地交换
• 3. 代码

• 利用HashSet的元素不可重复性，当添加失败时，表示该元素重复出现。

• 当没有重复元素时，0~n-1范围内的元素在长度为n的数组中升序排列可以得到nums[i]=i，即元素的值与所在位置的下标是相等的。

• 遍历数组，若元素不在该位置，则将其放到该位置，在此之前，如果该位置上已经存在相等元素，则表示该元素重复出现，返回即可。

import java.util.HashSet;
import java.util.Set;

public class Test {
    public static void main(String[] args) {
    }
}

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

class Solution1 {
    public int findRepeatNumber(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i) {
                if (nums[i] == nums[nums[i]]) {
                    return nums[i];
                }
                int temp = nums[nums[i]];
                nums[nums[i]] = nums[i];
                nums[i] = temp;
            }
        }
        return -1;
    }
}