剑指offer4J【C2 P3】找出数组中重复数字

题目

找出数组中重复的数字
数组中数字都在0~n之间,其中有些数字是重复的，但不知道谁重复，可能有1到多个重复的数字，请找出任意一个。

题解

解法1：

• 排序
• 遍历判断相邻相等性
  时间复杂度 Onlogn,空间复杂度 原数组排序 O1；

解法2：

• 哈希表
• 判断是否存在
  时间复杂度On,空间复杂度On 需要大小为n的哈希表

解法3：

• 归正下标
• 遍历数组，将数字放到对应的下标处，如果放置前该位置已经存在对应的数字则该数字即为重复数字。

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

源码: 剑指offer4J