【题目】
集合 S
包含从1到 n
的整数。不幸的是,因为数据错误,导致集合里面某一个元素复制了成了集合里面的另外一个元素的值,导致集合丢失了一个整数并且有一个元素重复。
给定一个数组 nums
代表了集合 S
发生错误后的结果。你的任务是首先寻找到重复出现的整数,再找到丢失的整数,将它们以数组的形式返回。
示例 1:
输入: nums = [1,2,2,4]
输出: [2,3]
注意:
【思路】
最直接的想法:使用字典,key为元素,value为出现次数,找到次数为2的元素;接着从1到n遍历,判断哪个元素不再字典中。
另外一种奇妙的想法:计算所有元素的和sum1;使用set求得唯一元素,计算其和sum2;同时计算1到n的和sum3=1+2+…+n=n*(n+1)/2;那么缺失的元素为sum3-sum2,多余的元素为sum1-sum2。
【代码】
python版本
方法一
class Solution(object):
def findErrorNums(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
d = {}
for n in nums:
d[n] = d.get(n, ) +
res = [, ]
for i in range(, len(nums)+):
if i not in d:
res[] = i
elif d[i] == :
res[] = i
return res
方法二
class Solution(object):
def findErrorNums(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
length = len(nums)
sum1 = length * (length+) /
sum2 = sum(set(nums))
return [sum(nums) - sum2, sum1 - sum2]
C++版本
方法一
class Solution {
public:
vector<int> findErrorNums(vector<int>& nums) {
int length = nums.size();
map<int, int> d;
vector<int> res;
for(auto n:nums){
if(d.find(n) == d.end())
d[n] = ;
else
res.push_back(n);
}
for(int i=; i<length+; i++){
if(d.find(i) == d.end()){
res.push_back(i);
break;
}
}
return res;
}
};
方法二
class Solution {
public:
vector<int> findErrorNums(vector<int>& nums) {
int length = nums.size();
int sum1 = length * (length+) / ;
int sum2 = ;
int repeat_num;
map<int, int> d;
for(auto n: nums){
sum2 += n;
if(d.find(n) == d.end())
d[n] = ;
else
repeat_num = n;
}
vector<int> res;
res.push_back(repeat_num);
res.push_back(sum1 - (sum2 - repeat_num));
return res;
}
};