服装公司网站建设方案/软件开发平台

645. 错误的集合 - 力扣（LeetCode）

没有说数组是否是有序的。

一次遍历+辅助数组，可以找到重复元素；
而丢失的元素通过数组元素和与本来的数组元素和(等差数列)可以计算出来。

class Solution {
public:vector<int> findErrorNums(vector<int>& nums) {int n = nums.size();vector<int> flags(n+1, 0);int idx = 0, sum = 0;for(int i = 0; i < n; ++i){sum += nums[i];if(flags[nums[i]] == 0) flags[nums[i]] = 1;else idx = i;//nums[idx]为重复的元素}int val = sum - n*(n+1)/2;return {nums[idx], nums[idx] - val};}
};

时间复杂度和空间复杂度都是o(n)。或者直接计数，重复元素出现两次，丢失元素出现0次：

class Solution {
public:vector<int> findErrorNums(vector<int>& nums) {int n = nums.size();vector<int> flags(n+1, 0);int idx = 0, sum = 0;for(int i = 0; i < n; ++i)  ++flags[nums[i]];int dup, miss;for(int i = 1; i <= n; ++i){if(flags[i] == 0)   miss = i;else if(flags[i] == 2)  dup = i;}return {dup, miss};}
};

那是否有时间复杂度o(n)，空间复杂度o(1)的方法呢？

class Solution {
public:vector<int> findErrorNums(vector<int>& nums) {int n = nums.size();int dup = -1, miss = -1;for(int i = 0; i < n; ++i){int v = abs(nums[i]);if(nums[v-1] < 0)//该数字已经出现过dup = v;else    nums[v-1] *= -1;//标记}for (int i = 0; i < n; ++i) {if (nums[i] > 0)    miss = i + 1;}return {dup, miss};}
};

还可以使用剑指 Offer 03. 数组中重复的数字_zj-CSDN博客里面原地置换的思路，可以寻找到重复的元素。有了重复元素之后，计算确实元素可以使用求和的方法，也可以使用上一种方法。

class Solution {
public:vector<int> findErrorNums(vector<int>& nums) {int n = nums.size();int sum = accumulate(nums.begin(), nums.end(), 0);int dup = -1;for(int i = 0; i < n; ++i){while(nums[i] != i+1){if(nums[i] == nums[nums[i]-1]){dup = nums[i];//找到重复元素break;}   swap(nums[i], nums[nums[i]-1]);//int tmp = nums[nums[i]-1];//nums[nums[i]-1] = nums[i];//nums[i] = tmp;}}int val = sum - n*(n+1)/2;//数学方法求缺失元素return {dup, dup-val};}
};