寻找重复数

发表于 2019-12-31 分类于 leetcode 阅读次数：

寻找重复数（难度：中等）

1

方法一：排序

复杂度

时间复杂度：O(nlog(n))。

空间复杂度：O(1) (or O(n))，在这里，我们对 nums 进行排序，因此内存大小是恒定的。如果我们不能修改输入数组，那么我们必须为 nums 的副本分配线性空间，并对其进行排序。

代码

class Solution {
    public int findDuplicate(int[] nums) {
        Arrays.sort(nums);
        for(int i = 1; i < nums.length; i++){
            if(nums[i]==nums[i-1])
                return nums[i];
        }
        return -1;
    }
}

2

方法二：集合（哈希表）

复杂度

时间复杂度：O(n)

空间复杂度：O(n)

代码

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

3

0%