剑指offer_03剑指Offer03数组中重复的数字

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

坚持就是胜利

这题并不难，用一个哈希表就能解决，但是哈希表最坏的时空复杂度是O(n),O(n)
这题难点在于怎样缩小时空复杂度

原地调换就可将空间复杂度缩小到O(1)

 * 思路：将对应位置的数字归位
 * 归位的时候遇到重复的，就找到了重复的数字，
 * 时间复杂度O(n)
 * 空间复杂度O(1)

    class Solution {
        public int findRepeatNumber(int[] nums) {
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] != i) {//当前位置和数字不等
                    //将当前位置的数字和它真正所在位置的数字交换
                    if (nums[nums[i]] == nums[i]){ //先判断对应位置是否已经有了真正的主人
                        return nums[i];
                    }
                    int copy = nums[nums[i]];
                    nums[nums[i]] = nums[i];
                    nums[i] = copy;
                    i--;
                }
            }
            return -1;
        }
    }