来一遍《剑指Offer》03. 数组中重复的数字

专栏前言:

本专栏主要是算法训练，目的很简单。但是过程需要坚持，就看能否坚持到最后，成为那个比较黑的，找到那个感觉。

找出数组中重复的数字。

题目描述：

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例：
示例 1：

输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3 

限制：

2 <= n <= 100000

解题1：

对数组进行排序，一前一后查找数字，如果相同则输出，不同则同时后移。

class Solution {
    
    public int findRepeatNumber(int[] nums) {
    
        Arrays.sort(nums);
        int low = 0, fast = 1;
        while(fast < nums.length){
    
            if(nums[low] != nums[fast]){
    
                low++;
                fast++;
            }else{
    
                return nums[low];
            }
        }
        return -1;
    }
}

时间 O(nlog_n)
空间 O(logn)

解题2：

利用 Hashset 的特点来记录数组中的数字，如果哈希表中存在该数字则输出，否则将该数字加入到Hash表中。

class Solution {
    
    public int findRepeatNumber(int[] nums) {
    
        Set<Integer> temps = new HashSet<>();
        for(int num:nums){
    
            if(temps.contains(num)){
    
                return num;
            }
            temps.add(num);
        }
        return -1;
    }
}

时间复杂度 O(N) ： 遍历数组使用 O(N) ，HashSet 添加与查找元素皆为 O(1)。
空间复杂度 O(N) ： HashSet 占用 O(N) 大小的额外空间。