Java&C++题解与拓展——leetcode442.数组中重复的数据【么的新知识】

每日一题做题记录，参考官方和三叶的题解

目录

• 题目要求
• 思路一：原地哈希
• • Java
  • C++
• 思路二：正负号标记
• • Java
  • C++
• 总结

题目要求

思路一：原地哈希

• 按正常排序的话 a a a应该在数组中 a − 1 a-1 a−1的位置，也就是 n u m s [ a − 1 ] = a nums[a-1]=a nums[a−1]=a；
• 那就遍历数组中的每一个数，把它们放在正确的位置上；
• 在放的过程中若该位置已有正确的数，那说明重复了，当前数加入答案，同时把当前数置为负数表示已处理过；
• 否则就交换这两个数的位置。

Java

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> res = new ArrayList<>();
        int n = nums.length;
        for(int i = 0; i < n; i++) {
            int cur = nums[i];
            if(cur < 0 || cur - 1 == i) // 遍历过 或 已就位
                continue;
            if(nums[cur - 1] == cur) { // 目标位置已就位
                res.add(cur);
                nums[i] *= -1; // 置负数表示已遍历
            }
            else { // 交换位置使其就位
                int tmp = nums[cur - 1];
                nums[cur - 1] = cur;
                nums[i--] = tmp;
            }
        }
        return res;
    }
}

• 时间复杂度： O ( n ) O(n) O(n)
• 空间复杂度： O ( 1 ) O(1) O(1)

C++

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> res;
        int n = nums.size();
        for(int i = 0; i < n; i++) {
            int cur = nums[i];
            if(cur < 0 || cur - 1 == i) // 遍历过 或 已就位
                continue;
            if(nums[cur - 1] == cur) { // 目标位置已就位
                res.push_back(cur);
                nums[i] *= -1; // 置负数表示已遍历
            }
            else { // 交换位置使其就位
                int tmp = nums[cur - 1];
                nums[cur - 1] = cur;
                nums[i--] = tmp;
            }
        }
        return res;
    }
};

• 时间复杂度： O ( n ) O(n) O(n)
• 空间复杂度： O ( 1 ) O(1) O(1)

思路二：正负号标记

• 其实和上面思路差不多，只不过不交换位置，只是用正负号做标记；
• 将当前数应该去的位置的值置为负数；
• 遍历时发现负则重复。

Java

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> res = new ArrayList<>();
        int n = nums.length;
        for(int i = 0; i < n; i++) {
            int cur = Math.abs(nums[i]); // 取原始数据
            if(nums[cur - 1] > 0) // 置为负表示遍历过
                nums[cur - 1] *= -1;
            else // 负表示已有该数
                res.add(cur);            
        }
        return res;
    }
}

• 时间复杂度： O ( n ) O(n) O(n)
• 空间复杂度： O ( 1 ) O(1) O(1)

C++

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> res;
        int n = nums.size();
        for(int i = 0; i < n; i++) {
            int cur = abs(nums[i]); // 取原始数据
            if(nums[cur - 1] > 0) // 置为负表示遍历过
                nums[cur - 1] *= -1;
            else // 负表示已有该数
                res.push_back(cur);            
        }
        return res;
    }
};

• 时间复杂度：$ O(n)$
• 空间复杂度： O ( 1 ) O(1) O(1)

总结

虽然是个中等题，但还是一下就想到了排序，只不过没想到这么巧妙的标记法，还要加油呀。

倒是比昨天的题简单太多……

欢迎指正与讨论！