?645. 錯(cuò)誤的集合

難度：簡(jiǎn)單

集合 s 包含從 1 到 n 的整數(shù)。不幸的是，因?yàn)閿?shù)據(jù)錯(cuò)誤，導(dǎo)致集合里面某一個(gè)數(shù)字復(fù)制了成了集合里面的另外一個(gè)數(shù)字的值，導(dǎo)致集合 丟失了一個(gè)數(shù)字 并且 有一個(gè)數(shù)字重復(fù) 。

給定一個(gè)數(shù)組 nums 代表了集合 S 發(fā)生錯(cuò)誤后的結(jié)果。

請(qǐng)你找出重復(fù)出現(xiàn)的整數(shù)，再找到丟失的整數(shù)，將它們以數(shù)組的形式返回。

示例 1：

輸入：nums = [1,2,2,4]
輸出：[2,3]

示例 2：

輸入：nums = [1,1]
輸出：[1,2]

提示：

• $2<=nums.length<=10^4$
• $1<=nums[i]<=10^4$

??思路：

法一：交換數(shù)組元素

最直接的方法是先對(duì)數(shù)組進(jìn)行排序，這種方法時(shí)間復(fù)雜度為 $O(nlogn)$。本題可以以 $O(n)$ 的時(shí)間復(fù)雜度、$O(1)$ 空間復(fù)雜度來(lái)求解。

• 主要思想是通過(guò)交換數(shù)組元素，使得數(shù)組上的元素在正確的位置上；
• 這樣只有 重復(fù)的數(shù) 出現(xiàn)在 丟失整數(shù) 的位置上。

法二：哈希表

重復(fù)的數(shù)字在數(shù)組中出現(xiàn) 2 次，丟失的數(shù)字在數(shù)組中出現(xiàn) 0次，其余的每個(gè)數(shù)字在數(shù)組中出現(xiàn) 1 次。因此可以使用哈希表記錄每個(gè)元素在數(shù)組中是否出現(xiàn)

• 如果出現(xiàn)兩次，則找到了重復(fù)的數(shù)；
• 將所有數(shù)都存到哈希表，再遍歷哈希表，則可找到丟失的數(shù)；

??代碼：(Java、C++)

法一：交換數(shù)組元素
Java

class Solution {
    public int[] findErrorNums(int[] nums) {
        for(int i = 0; i < nums.length; i++){
            while(nums[i] != i + 1 && nums[i] != nums[nums[i] - 1]){
                swap(nums, i, nums[i] - 1);
            }
        }
        for(int i = 1; i <= nums.length; i++){
            if(nums[i - 1] != i){
                return new int[]{nums[i - 1], i};
            }
        }
        return null;
    }
    private void swap(int[] nums, int i, int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

C++

class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        for(int i = 0; i < nums.size(); i++){
            while(nums[i] != i + 1 && nums[i] != nums[nums[i] - 1]){
                swap(nums, i, nums[i] - 1);
            }
        }
        for(int i = 1; i <= nums.size(); i++){
            if(nums[i - 1] != i){
                return {nums[i - 1], i};
            }
        }
        return {};
    }
    void swap(vector<int>& nums, int i, int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
};

法二：哈希表
Java

class Solution {
    public int[] findErrorNums(int[] nums) {
        HashSet<Integer> s = new HashSet<>();
        int repeat = 0, lose = 0;
        for(int num : nums){
            if(s.contains(num)) repeat = num;
            s.add(num);
        }
        for(int i = 1; i <= nums.length; i++){
            if(!s.contains(i)){
                lose = i;
                break;
            }
        }
        return new int[]{repeat, lose};
    }
}

C++

class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        unordered_set<int> s;
        int repeat = 0, lose = 0;
        for(int num : nums){
            if(s.find(num) != s.end()) repeat = num;
            s.insert(num);
        }
        for(int i = 1; i <= nums.size(); i++){
            if(s.find(i) == s.end()){
                lose = i;
                break;
            }
        }
        return {repeat, lose};
    }
};

?? 運(yùn)行結(jié)果：

?? 復(fù)雜度分析：

• 時(shí)間復(fù)雜度：$O(n)$，其中 n 為數(shù)組的長(zhǎng)度。
• 空間復(fù)雜度：$O(1)$，法一只需常量級(jí)空間；而哈希表需要?jiǎng)?chuàng)建大小為 $O(n)$ 的哈希表，空間復(fù)雜度為$O(n)$。

題目來(lái)源：力扣。

放棄一件事很容易，每天能堅(jiān)持一件事一定很酷，一起每日一題吧！
關(guān)注我 leetCode專(zhuān)欄，每日更新！文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-440959.html

注： 如有不足，歡迎指正！

到了這里，關(guān)于( 數(shù)組和矩陣) 645. 錯(cuò)誤的集合 ——【Leetcode每日一題】的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！