Problem: 645. 錯誤的集合

題目描述

思路

1.排序

1.對nums數組按從小到大的順序排序;
2.遍歷數組時若判斷兩個相鄰的元素則找到重復元素；
3.記錄一個整形變量prev一次置換當前位置元素并與其作差，若差等于2著說明缺失的數即為這中間的一個數（由于缺失的數可能是1，則初始化prev為0）
4.由于nums中本該記錄1-n，則若nums[n - 1] != n,則說明缺失的數是n；

2.哈希表

1.對nums中的元素進行統計（以其大小為鍵，出現的次數為值）；
2.從1-n開始遍歷，若某一個值出現2次則為重復元素，若一個值沒有出現（其值為0）則為缺失值

復雜度

思路1：
時間復雜度:

$O(nlogn)$；其中$n$為數組nums的大小

空間復雜度:

$O(n)$

思路2 ：
時間復雜度:

$O(n)$

空間復雜度:

$O(n)$

Code

思路1：

class Solution {
public:/*** Sort* * @param nums Given array* @return vector<int>*/vector<int> findErrorNums(vector<int>& nums) {int n = nums.size();vector<int> res(2);sort(nums.begin(), nums.end());int prev = 0;for (int i = 0; i < n; ++i) {int curr = nums[i];if (curr == prev) {res[0] = prev;} else if (curr - prev > 1) {res[1] = prev + 1;}prev = curr;}if (nums[n - 1] != n) {res[1] = n;}return res;}
};

思路2：

class Solution {
public:/*** Hash* * @param nums Given array* @return vector<int>*/vector<int> findErrorNums(vector<int>& nums) {vector<int> res(2);int n = nums.size();unordered_map<int, int> map;for (auto& num : nums) {map[num]++;}for (int i = 1; i <= n; ++i) {int count = map[i];if (count == 2) {res[0] = i;} else if (count == 0) {res[1] = i;}}return res;}
};