LeetCode 645. Set Mismatch. C++

645. Set Mismatch

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.

Input: nums = [1,2,2,4]
Output: [2,3]

解法1 map

要找出数组中缺失的元素和重复的元素,我的第一反应是,如果知道数组中每个元素出现的次数,问题就迎刃而解,而map正好可以储存这种一对一的关联。

class Solution {
public:
vector<int> findErrorNums(vector<int>& nums) {
vector<int> result(2,0);
map<int,int> m1;
for(int i=1;i<nums.size()+1;i++){
m1[nums[i-1]]+=1;
}
for(int i=1;i<nums.size()+1;i++){
if(m1[i]==0) result[1]=i;
else if(m1[i]==2) result[0]=i;
}
return result;
}
};

解法2 数组计数

跟上面一个思路,只不过改成数组count来计数。数组count元素的下标指代nums中1到n的数,比如count[3]=2意思是nums中元素3出现的次数是2,所以数组count长度为nums.size()+1。

class Solution {
public:
vector<int> findErrorNums(vector<int>& nums) {
vector<int> result(2,0);
vector<int> count(nums.size()+1,0);
for(int i=1;i<nums.size()+1;i++){
count[nums[i-1]] ++;
}
for (int i=1; i<nums.size()+1;i++){
if (count[i]==0) result[1]=i;
else if (count[i]==2) result[0]=i;
}
return result;
}
};

解法3 数学法

先遍历找到数组中的重复元素repet,顺便对数组求和sum,从1到n的整数数组即等差数列求和为n*(n+1)/2,它们的差值就来源于那个被替换掉的数。

比如,[1,2,2,4]重复元素是2,1+2+2+4=9;原本是[1,2,3,4],1+2+3+4=10;说明重复的2导致数组总和少了1,即被2替换掉的元素应该比2大1,是3。

这种方法因为需要求和,所以遍历数组时即使找到了repet也不能break,用时不太理想。

class Solution {
public:
vector<int> findErrorNums(vector<int>& nums) {
sort(nums.begin(),nums.end());
int len=nums.size();
int repet,lost;
int sum=nums[0];
for(int i=1;i<len;i++){
if(nums[i]==nums[i-1]){
repet=nums[i];
}
sum=sum+nums[i];
}
lost=repet-(sum-len*(len+1)*0.5);
return {repet,lost};
}
};

解法4 暴力法

单独检查 1 到 n 所有数字,检查每个数字时都遍历整个数组,检查当前数字在数组中是否出现了两次,或者一次都没有出现。逻辑上没问题,但是超时。

class Solution {
public:
vector<int> findErrorNums(vector<int>& nums) {
int len=nums.size();
int repet=0,lost=0;
vector<int> count(len, 0);
for(int i=0;i<len;i++){
for(int x:nums){
if(x==i+1) count[i]++;
}
if(count[i]==0) lost=i+1;
else if(count[i]==2) repet=i+1;
if(lost>0 && repet>0) break;
}
return {repet,lost};
}
};

解法5 排序

先把数组排序,遍历,如果后一个与前一个差值是0说明有重复,如果差值是2说明有缺失。
注意,如果缺失的是第一个或最后一个元素,会有点不一样,所以lost初始化为1就是考虑到第一个元素缺失的情况;nums[len-1]==len?lost:len是考虑到最后一个元素缺失的情况。

class Solution {
public:
vector<int> findErrorNums(vector<int>& nums) {
sort(nums.begin(),nums.end());
int len=nums.size();
int repet=0,lost=1;
for(int i=1;i<len;i++){
int ans=nums[i]-nums[i-1];
if(ans==0) repet=nums[i];
else if(ans==2) lost=nums[i-1]+1;
}
return {repet,nums[len-1]==len?lost:len};
}
};

经验

1.C++ Map的使用
https://blog.csdn.net/BAR_WORKSHOP/article/details/108415239

2.C++ 条件表达式

(条件表达式) ? (条件为真时的表达式) : (条件为假时的表达式)

“……?……:……”称为条件操作符,它的运算优先级比逻辑或还低,是目前为止优先级最低的操作符。含有条件操作符的表达称为条件表达式。既然是表达式,它就应该有一个计算结果,而这个结果就是经过判断而得到的结果,可以定义一个变量来存放这个结果,也可以用输出语句把这个结果输出。

原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

LeetCode 645. Set Mismatch. C++

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » LeetCode 645. Set Mismatch. C++
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏