【LeetCode100】--- 寻找重复数

用户11288958

发布于 2025-01-21 12:49:33

2590

文章被收录于专栏：学习学习

题目传送门

方法一：暴力解法（超时）

算法原理

双重循环，每次固定一个数，再遍历别的数。比较这两个数是否相等，若相等则返回这个数。就是重复数。

复杂度分析

时间复杂度：O（N方）空间复杂度：O（1）

代码：

class Solution {
    public int findDuplicate(int[] nums) {
        int n = nums.length;

        for(int i = 0; i < n-1; i++){
            for(int j = i+1; j < n; j++){
                if(nums[i] == nums[j]){
                    return nums[i];
                }
            }
        }
        return -1;
    }
}

方法二：哈希表（数组模拟）

算法原理

建立一个大小为n的数组，用来模拟哈希表。以各个数字作为下标，来统计各个数字出现的次数。最终遍历这个哈希数组，若有大于1的数，则返回这个下标就是重复出现的数字。

代码：

class Solution {
    public int findDuplicate(int[] nums) {
        int n = nums.length;
        int[] hash = new int[n];

        for(int i = 0; i < n; i++){
            hash[nums[i]]++;
        }

        for(int i = 0; i < n; i++){
            if(hash[i] > 1){
                return i;
            }
        }
        return -1;
    }
}

复杂度分析

时间复杂度：O(N) 为这个数组的长度空间复杂度：O（N）为这个数组的长度

方法三：哈希表（HashSet）

算法原理

创建HashSet这个哈希表。遍历数组，如果这个数字在哈希表中出现了，那么就返回这个数如果没有出现，那么就将这个数添加到哈希表中。

class Solution {
    public int findDuplicate(int[] nums) {
        Set<Integer> seen = new HashSet<>();

        for(int n : nums){
            if(seen.contains(n)){
                return n;
            }
            seen.add(n);
        }
        return -1;
    }
}