🎈 作者：Linux猿

🎈 简介：CSDN博客专家🏆，华为云享专家🏆，Linux、C/C++、云计算、物联网、面试、刷题、算法尽管咨询我，关注我，有问题私聊！

🎈 关注专栏： 数据结构和算法成神路【精讲】优质好文持续更新中……🚀🚀🚀

🎈 欢迎小伙伴们点赞👍、收藏⭐、留言💬

一、题目描述

给定一个包含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。

提示：

n == nums.length

1 <= n <= 10^5

1 <= nums[i] <= n

进阶：你能在不使用额外空间且时间复杂度为 O(n) 的情况下解决这个问题吗? 你可以假定返回的数组不算在额外空间内。

二、测试样例

输入：nums = [4,3,2,7,8,2,3,1]

输出：[5,6]

说明：在数组 nums 中，只有 5 和 6 没有出现在 [1,8] 的区间内。

三、算法思路

首先需要注意的是，本题要求使用的时间复杂度为 O(n)，且不使用额外空间。

那么，可以确定的是只需要遍历常数次 nums 数组，不开辟额外的非常数级的空间，可以在原数组上修改，有这些条件限制后，能想到的解决方法就很局限了。

我们可以用下标标识[1, n] 之前的数字，遍历数组 nums，将以 nums[i] 为下标所标识的数组值加 n，一直遍历完数组，这样，如果 nums[i] < n ，表示 nums[i] 并没有加 n，所以 i 没有出现在[1,n]的区间中。

注意：因为是存储在数组中，下标从 0 开始，所以使用下标 i 表示数字 i - 1。 

四、代码实现

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        int n = nums.size();
        for(int i = 0; i < n; ++i) {
            int idx = (nums[i] - 1)%n;
            nums[idx] = nums[idx] + n;
        }
        vector<int> ans;
        for(int i = 0; i < n; ++i) {
            if(nums[i] <= n) {
                ans.push_back(i+1);
            }
        }
        return ans;
    }
};


int main()
{
    Solution obj;
    int a[] = {4, 3, 2, 7, 8, 2, 3, 1};
    vector<int>ans(a, a + 8);
    ans = obj.findDisappearedNumbers(ans);
    for(int i = 0; i < ans.size(); ++i) {
        cout<<ans[i]<<" ";
    }
    cout<<endl;
    return 0;
}

五、复杂度分析

5.1 时间复杂度

时间复杂度：O(n)，在上述算法中，使用了两层  for 循环，所以时间复杂度为 O(n)。

5.2 空间复杂度

空间复杂度：O(n)，在上述算法中，使用 ans 存储最终的结果，所以空间复杂度为 O(n)。

六、总结

本题是一道很好的想法题，题目进行了很强的限制，需要结合题目限制来解题，这样更能想到解题方法。

🎈 作者：Linux猿

🎈 简介：CSDN博客专家🏆，华为云享专家🏆，Linux、C/C++、云计算、物联网、面试、刷题、算法尽管咨询我，关注我，有问题私聊！

🎈 关注专栏： 数据结构和算法成神路【精讲】优质好文持续更新中……🚀🚀🚀

🎈 欢迎小伙伴们点赞👍、收藏⭐、留言💬