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

难度: 🌕

问题描述

---

解法 1 - 原地交换

class Solution {
    public int findRepeatNumber(int[] nums) {
        // 思路：
        // 遍历数组，将每个元素放在应该的下标位置，遇到重复的就是结果
        int len = nums.length;
        int index = 0;
        while(index < len) {
            if(nums[index] == index) {
                index ++;
                continue;
            } 
            // 尝试将 [index] 放到 [index] 处
            // 若 [index] 处已经有了正确的值，返回该值
            int exp = nums[nums[index]];
            if(exp == nums[index]) {
                return nums[index];
            }
            swap(nums, index, nums[index]);
        }
        return -1;
    }

    private void swap(int[] nums, int a, int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }
}

---

输出

---

解法 2 - HashSet

class Solution {
    public int findRepeatNumber(int[] nums) {
        // 思路：
        // 借助 HashSet，只有出现重复的数字，就是所求
        HashSet<Integer> set = new HashSet<>();
        for(int i : nums) {
            if(set.contains(i)) {
                return i;
            } else {
                set.add(i);
            }
        }
        return -1;
    }
}

---

输出