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

哈希表/set

class Solution {

    public int findRepeatNumber(int[] nums) {

        HashSet<Integer> set = new HashSet<>();

        for(int num : nums){

            if(set.contains(num))

                return num;

            set.add(num);

        }

        return -1;

    }

}

思路：利用set的特性

原地置换

class Solution {

    public int findRepeatNumber(int[] nums) {

        for(int i =  0; i < nums.length; i++){

            while(nums[i] != i){

                if(nums[nums[i]] == nums[i])

                    return nums[i];

                int temp = nums[nums[i]];

                nums[nums[i]] = nums[i];

                nums[i] = temp;

            }

        }

        return -1;

    }

}

思路：遍历数组并通过交换操作，使元素的索引与值一一对应，如果在交换过程中发现两值相同则返回。（因为一个索引对应一个值）