448. Find All Numbers Disappeared in an Array&&645. Set Mismatch

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目：

448. Find All Numbers Disappeared in an Array

Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements of [1, n] inclusive that do not appear in this array.

Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

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.

思路：

448和645具有相似的思路。两道题的共同点在于：元素的大小均为 [1,n]。448要求找出未出现的数字，645要求找出出现了两次的数字和未出现的数字。

由于元素的下标为[0,n-1]，则元素的大小减去1得到的即为某个元素的下标，因此可以利用元素大小与下标之间的关系寻找特殊的数字。

对于448，遍历整个数组，通过元素的大小减去1得到下标。若该下标对应的元素为正，则将其乘以-1，变为负数；若该下标对应的元素为负，证明该下标之前已经出现过了一次，不作处理。通过这一次的遍历，仍然为正的元素所对应的下标再加1即为未出现过的元素。

对于645，遍历整个数组，通过元素的大小减去1得到下标。若该下标对应的元素为正，则将其乘以-1，变为负数；若该下标对应的元素为负，证明该下标之前已经出现过了一次，将该下标+1加入result中。通过这一次的遍历，仍然为正的元素所对应的下标再加1即为未出现过的元素。

代码：

448.

class Solution {
public:
vector<int> findDisappearedNumbers(vector<int>& nums) {
vector<int> ans;
for (int i = ; i < (signed) nums.size(); i++) {
int index = abs(nums[i]) - ;
if (nums[index] > )
nums[index] *= -;
else
continue;
}
for (int i = ; i < (signed) nums.size(); i++)
if (nums[i] > )
ans.push_back(i + );
return ans;
}
};

645.

class Solution {
public:
vector<int> findErrorNums(vector<int>& nums) {
vector<int> ans;
for (int i = ; i < (signed) nums.size(); i++) {
int index = abs(nums[i]) - ;
if (nums[index] > ) {
nums[index] *= -;
} else {
ans.push_back(index + );
}
}
for (int i = ; i < (signed) nums.size(); i++) {
if (nums[i] > )
ans.push_back(i + );
}
return ans;
}
};

448. Find All Numbers Disappeared in an Array&&645. Set Mismatch的更多相关文章

【leetcode】448&period; Find All Numbers Disappeared in an Array
problem 448. Find All Numbers Disappeared in an Array solution: class Solution { public: vector<i ...
leetcode 217&period; Contains Duplicate 287&period; Find the Duplicate Number 442&period; Find All Duplicates in an Array 448&period; Find All Numbers Disappeared in an Array
后面3个题都是限制在1-n的,所有可以不先排序,可以利用巧方法做.最后两个题几乎一模一样. 217. Contains Duplicate class Solution { public: bool ...
448&period; Find All Numbers Disappeared in an Array【easy】
448. Find All Numbers Disappeared in an Array[easy] Given an array of integers where 1 ≤ a[i] ≤ n (n ...
448&period; Find All Numbers Disappeared in an Array&commat;python
Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and ot ...
5&period; Leetcode 448&period; Find All Numbers Disappeared in an Array
Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and ot ...
LeetCode 448&period; Find All Numbers Disappeared in an Array （在数组中找到没有出现的数字）
Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and ot ...
leetcode 448&period; Find All Numbers Disappeared in an Array -easy (重要)
题目链接: https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/description/ 题目描述: Give ...
LeetCode 448 Find All Numbers Disappeared in an Array 解题报告
题目要求 Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice a ...
[LeetCode&amp&semi;Python] Problem 448&period; Find All Numbers Disappeared in an Array
Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and ot ...

随机推荐

关于用sql语句实现一串数字位数不足在左侧补0的技巧
在日常使用sql做查询插入操作时,我们通常会用到用sql查询一串编号,这串编号由数字组成.为了统一美观,我们记录编号时,统一指定位数,不足的位数我们在其左侧补0.如编号66,我们指定位数为5,则保存数 ...
Lamp和Lnmp环境搭建
一.安装Lamp wget -c http://soft.vpser.net/lnmp/lnmp1.2-full.tar.gz && tar zxf lnmp1.2-full.tar. ...
总结的一些PHP开发中的tips
总结的一些PHP开发中的tips 发布时间:2013-05-28 12:47:44 来源: 评论:0 点击: 次 [字号:大中小] QQ空间新浪微博腾讯微博人人网豆瓣网百度空间百度搜藏开心 ...
CSS 学习质料
1.学习CSS布局 http://zh.learnlayout.com/display.html
用Navicat连接Oracle数据库时报错ORA-28547&colon;connection to server failed,probable Oracle Net admin error
用Navicat连接Oracle数据库时出现如下错误上网一查原来是oci.dll版本不对.因为Navicat是通过Oracle客户端连接Oracle服务器的,Oracle的客户端分为两种,一种是标准 ...
经常使用MD5算法代码
经常使用的MD5算法代码日期: 2014年8月4日作者: 铁锚 MD5,全称为 Message Digest Algorithm 5(消息摘要算法第五版).详情请參考维基百科:MD5 MD5加密后 ...
《NLTK基础教程》译者序
购买<NLTK基础教程> 说来也凑巧,在我签下这本书的翻译合同时,这个世界好像还不知道AlphaGo的存在.而在我完成这本书的翻译之时,Master已经对人类顶级高手连胜60局了.至少从媒 ...
shell脚本：Kill掉MySQL中所有sleep的client线程
分享一个shell脚本,实现kill掉mysql中所有的sleep状态的client线程,有需要的朋友,可以参考研究下. 文件名称:killsleep.sh. #It is used to kill ...
jQuery ajax中serialize()方法增加其他参数
表单提交使用jQuery.ajax()进行表单提交时,需要传递参数,最直接的方法便是使用Form的serializa()将表单序列化,前提只是将Form表单中的name属性与数据库的字段名保持一致便 ...
mysql|中主外键关系(转）
http://my.oschina.net/liting/blog/356150 一.外键: 1.什么是外键 2.外键语法 3.外键的条件 4.添加外键 5.删除外键 1.什么是外键: 主键:是唯一标 ...