题目描述:
The set S
originally contains numbers from 1 to n
. But unfortunately, due to the data error, one of the numbers in the set got duplicated to another number in the set, which results in repetition of one number and loss of another number.
Given an array nums
representing the data status of this set after the error. Your task is to firstly find the number occurs twice and then find the number that is missing. Return them in the form of an array.
Example 1:
代码语言:javascript复制Input: nums = [1,2,2,4]
Output: [2,3]
Note:
- The given array size will in the range [2, 10000].
- The given array's numbers won't have any order.
要完成的函数:
vector<int> findErrorNums(vector<int>& nums)
说明:
1、之前就做过一道类似的题目,给定一个长度为n的vector,里面原本要出现从1到n的所有元素,但是有一个元素没有出现,而有另一个元素出现了两次。要找出这个没有出现的元素。那道题目会做了,这道题目再加上异或的处理方法,也就能迅速得到答案。
之前类似题目的博文leetcode-448-Find All Numbers Disappeared in an Array
2、所以我们使用了之前的方法,再加上异或的熟悉套路,构造如下代码:
代码语言:javascript复制 vector<int> findErrorNums(vector<int>& nums)
{
int s1=nums.size();
int t,miss,p=0;for(int i=0;i<s1;i )//之前题目的思路
{
if(nums[abs(nums[i])-1]<0)
continue;
else
{
t=abs(nums[i])-1;
nums[t]*=-1;
}
}
for(int i=0;i<s1;i )//找到没有出现的值
{
if(nums[i]>0)
miss=i 1;
}
for(int i=0;i<s1;i )//得到"出现两次的值"和"没有出现的值"的异或结果
{
p^=abs(nums[i])^(i 1);
}
p^=miss;//出现两次的值存储在p中
return {p,miss};
}
上述代码由于改变了nums中的数值,所以最后还要再abs一次,这里做得不是很好。
在discuss区还看到了其他找到“没有出现的值”的方法,而不需要改变nums中的值,这样做会更好。同学们可以自己参照着看。
上述代码实测36ms,beats 96.45% of cpp submissions。