leetcode link: 找到所有数组中消失的数字
给你一个含
n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。
示例 1：
输入：nums = [4,3,2,7,8,2,3,1] 输出：[5,6]示例 2：
输入：nums = [1,1] 输出：[2]空间复杂度为O(n)的解法：
- 哈希表：利用一个数组记录出现的数字，再遍历一下数组即可得到未出现的数组。
class Solution {
public:
vector findDisappearedNumbers(vector& nums) {
vector path(nums.size()+1, 0);
path[0] = 1;
vector result;
for(int i=0; i<nums.size(); i++){
path[nums[i]]++;
}
for(int i=1; i<=nums.size(); i++){
if (path[i] == 0) result.push_back(i);
}
return result;
}
};O(n) 的情况下解决这个问题吗? 你可以假定返回的数组不算在额外空间内。
空间复杂度为O(1)的解法，解题思路：
- 1 该题要求不能使用额外空间，故不能使用哈希表；
- 2 该题需要时间复杂度为O(n)故不能进行排序。
- 3 该题有信息：数组是1到n的数组，故我们可以在遍历的过程中将数组交换到其原本的位置。
- 4 遍历数组，如果数组索引处的值不等于索引，则加入到result数组。
class Solution {
public:
vector<int> findDisappearedNumbers(vector<int>& nums) {
vector<int> result;
int indice = 0, size = nums.size();
while(indice < size){
// nums[indice]-1为nums[indice]该在的索引下标
if (nums[indice] != nums[nums[indice]-1])
swap(nums[indice], nums[nums[indice]-1]);
else
indice++;
}
for(int i=0; i<size; i++){
if (nums[i] != i+1) result.push_back(i+1);
}
return result;
}
};