[LeetCode] 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.
Example:
Input: [4,3,2,7,8,2,3,1] Output: [5,6]
这道题让我们找出数组中所有消失的数,跟之前那道Find All Duplicates in an Array极其类似,那道题让找出所有重复的数字,这道题让找不存在的数,这类问题的一个重要条件就是1 ≤ a[i] ≤ n (n = size of array),不然很难在O(1)空间和O(n)时间内完成。三种解法也跟之前题目的解法极其类似。首先来看第一种解法,这种解法的思路路是,对于每个数字nums[i],如果其对应的nums[nums[i] - 1]是正数,我们就赋值为其相反数,如果已经是负数了,就不变了,那么最后我们只要把留下的整数对应的位置加入结果res中即可,参见代码如下:
解法一:
class Solution { public: vector<int> findDisappearedNumbers(vector<int>& nums) { vector<int> res; for (int i = 0; i < nums.size(); ++i) { int idx = abs(nums[i]) - 1; nums[idx] = (nums[idx] > 0) ? -nums[idx] : nums[idx]; } for (int i = 0; i < nums.size(); ++i) { if (nums[i] > 0) { res.push_back(i + 1); } } return res; } };
第二种方法是将nums[i]置换到其对应的位置nums[nums[i]-1]上去,比如对于没有缺失项的正确的顺序应该是[1, 2, 3, 4, 5, 6, 7, 8],而我们现在却是[4,3,2,7,8,2,3,1],我们需要把数字移动到正确的位置上去,比如第一个4就应该和7先交换个位置,以此类推,最后得到的顺序应该是[1, 2, 3, 4, 3, 2, 7, 8],我们最后在对应位置检验,如果nums[i]和i+1不等,那么我们将i+1存入结果res中即可,参见代码如下:
解法二:
class Solution { public: vector<int> findDisappearedNumbers(vector<int>& nums) { vector<int> res; for (int i = 0; i < nums.size(); ++i) { if (nums[i] != nums[nums[i] - 1]) { swap(nums[i], nums[nums[i] - 1]); --i; } } for (int i = 0; i < nums.size(); ++i) { if (nums[i] != i + 1) { res.push_back(i + 1); } } return res; } };
下面这种方法是在nums[nums[i]-1]位置累加数组长度n,注意nums[i]-1有可能越界,所以我们需要对n取余,最后要找出缺失的数只需要看nums[i]的值是否小于等于n即可,最后遍历完nums[i]数组为[12, 19, 18, 15, 8, 2, 11, 9],我们发现有两个数字8和2小于等于n,那么就可以通过i+1来得到正确的结果5和6了,参见代码如下:
解法三:
class Solution { public: vector<int> findDisappearedNumbers(vector<int>& nums) { vector<int> res; int n = nums.size(); for (int i = 0; i < n; ++i) { nums[(nums[i] - 1) % n] += n; } for (int i = 0; i < n; ++i) { if (nums[i] <= n) { res.push_back(i + 1); } } return res; } };
类似题目:
Find All Duplicates in an Array
参考资料:
https://discuss.leetcode.com/topic/65944/c-solution-o-1-space
https://discuss.leetcode.com/topic/66063/5-line-java-easy-understanding
相关文章
- [LeetCode] Move Zeroes - 整数数组处理问题
- Java实现 LeetCode 779 第K个语法符号(递归)
- Java实现 LeetCode 767 重构字符串(ASCII的转换)
- Java实现 LeetCode 761 特殊的二进制序列(括号问题)
- Java实现 LeetCode 753 破解保险箱(递归)
- Java实现 LeetCode 713 乘积小于K的子数组(子集数量+双指针)
- Java实现 LeetCode 713 乘积小于K的子数组(子集数量+双指针)
- Java实现 LeetCode 706 设计哈希映射(数组+链表)
- Java实现 LeetCode 629 K个逆序对数组(动态规划+数学)
- Java实现 LeetCode 540 有序数组中的单一元素(位运算入门)
- Java实现 LeetCode 215. 数组中的第K个最大元素
- Java实现 LeetCode 179 最大数
- Java实现 LeetCode 167 两数之和 II - 输入有序数组
- Java实现 LeetCode 33 搜索旋转排序数组
- 每日一道 LeetCode (14):数组加一
- LeetCode(21):合并两个有序链表
- Leetcode——第 329 场周赛
- LeetCode-234. 回文链表【链表,双指针】
- (“树” 之 前中后序遍历 ) 94. 二叉树的中序遍历 ——【Leetcode每日一题】
- Leetcode 2048. 下一个更大的数值平衡数(有点意思,已解决)
- Leetcode 1005. K 次取反后最大化的数组和(终于解决)
- Leetcode 1310. 子数组异或查询
- [LeetCode] 581. 最短无序连续子数组 ☆
- [LeetCode] 26. Remove Duplicates from Sorted Array ☆(从有序数组中删除重复项)
- leetcode 5. 最长回文子串
- 【Leetcode刷题Python】404. 左叶子之和