Offer.P3[数组中重复的数字]

方法一：原地哈希

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int findRepeatNumber(int[] nums) {
        int i = 0;
        while (i < nums.length) {
            if (nums[i] == i) {
                ++i;
                continue;
            }
            if (nums[i] == nums[nums[i]]) return nums[i];
            int temp = nums[i];
            nums[i] = nums[temp];
            nums[temp] = temp;
        }
        return -1;
    }
}
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(1)$