寻找消失的数字

举报
Linux猿 发表于 2022/02/21 21:04:30 2022/02/21
【摘要】 CSDN博客专家🏆,华为云享专家🏆,Linux、C/C++、云计算、物联网、面试、刷题、算法尽管咨询我,关注我,有问题私聊!


🎈 作者: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++、云计算、物联网、面试、刷题、算法尽管咨询我,关注我,有问题私聊!

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

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


【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。