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

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

利用题目的限制条件：所有数字都在 0～n-1 的范围内
通过交互让数字和下标一一对应，如果有多个数字对应同一个下标，那就找到了答案。

class Solution {
    public int findRepeatNumber(int[] nums) {
        int n = nums.length;
        int i = 0;
        while(i < n){
            if(nums[i] == i){  // 数字和下标对应了，往后寻找
                i++;
                continue;
            } 
            if(nums[nums[i]] == nums[i]) return nums[i];  // 有两个数字对应同一个下标了，找到重复数字了
            swap(nums, i, nums[i]);  // 把nums[i]换到正确的位置
        }

        return 0;
    }

    void swap(int[] nums, int i, int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

另一种写法

class Solution {
    public int findRepeatNumber(int[] nums) {
        int n = nums.length;
        for(int i = 0; i < n; i++){
            while(nums[i] != i) {
                if(nums[i] == nums[nums[i]]) return nums[i];
                swap(nums, i, nums[i]);
            }
        }
        return 0;
    }

    void swap(int[] nums, int i, int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}