首页 > 其他分享 >448.找到所有数组中消失的数字

448.找到所有数组中消失的数字

时间:2023-04-05 15:33:05浏览次数:48  
标签:448 数字 nums int vector 数组 ans position

找到所有数组中消失的数字

给你一个含 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]

提示:

n == nums.length
\(1 <= n <= 10^5\)
1 <= nums[i] <= n
进阶:你能在不使用额外空间且时间复杂度为 O(n) 的情况下解决这个问题吗? 你可以假定返回的数组不算在额外空间内。

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/find-all-numbers-disappeared-in-an-array
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路:哈希表

使用哈希表统计元素出现的次数。

code

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        int n = nums.size();

        vector<int> cnt(n + 1,0);

        for(auto item : nums) cnt[item]++;

        vector<int> ans;
        for(int i = 1;i <= n;i ++)
            if(cnt[i] == 0) ans.push_back(i);

        return ans;
    }
};

解题思路2:原地算法

见注释

code

class Solution {
public:
    //原地算法
    //以数组下标作为统作用(1-n)
    //遍历数组,元素对应的下标置为负数
    //最后数组中任然是正数的下标就是缺失的元素
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        
        for(int i = 0;i < nums.size();i ++)
        {
            int position = abs(nums[i]) - 1;

            if(nums[position] > 0) nums[position] = - nums[position];
            else continue;
        }

        vector<int> ans;

        for(int i = 0;i < nums.size();i ++)
        {
            if(nums[i] > 0) ans.push_back(i+1);
        }

        return ans;
    }
};

标签:448,数字,nums,int,vector,数组,ans,position
From: https://www.cnblogs.com/huangxk23/p/17289527.html

相关文章

  • LeetCode 81. 搜索旋转排序数组 II
    1classSolution{public:boolsearch(vector<int>&nums,inttarget){intindex=-1;for(inti=0;i<nums.size()-1;++i){if(nums[i]>nums[i+1])index=i;}if(index==-1){......
  • HJ64_MP3光标位置_数组_模拟思路_滑动窗口
    思路:用模拟跟踪U、D得输出的歌曲,用双指针跟踪歌曲当前窗口。注意,在第一首向上滑动,和最后一首向下滑是,窗口特殊跳动,此时双指针指向特殊处理。留意到,不管是特殊情况还是普通情况,指针上划时歌曲减一。如1调到10,10上划为9,视为减一。得到代码如下:importsysa=int(sys.stdin.......
  • JavaScript中数组元素删除的七大方法汇总
    原文链接:https://blog.csdn.net/u010323023/article/details/52700770 在JavaScript中,除了Object之外,Array类型恐怕就是最常用的类型了。与其他语言的数组有着很大的区别,JavaScript中的Array非常灵活。今天我就来总结了一下JavaScript中Array删除的方法。大致的分类可以分为如下......
  • ES6中一些方便的数组方法和对象方法
    //一共七个方法,其实,都是带有遍历性质的方法参考https://blog.csdn.net/PeaYing/article/details/100175757......
  • Go语言入门3(数组)
    数组​ 数组是具有相同唯一类型的一组已编号且长度固定的数据项序列(这是一种同构的数据结构);这种类型可以是任意的原始类型例如整形、字符串或者自定义类型(结构体、接口)。数组长度也是数组类型的一部分,所以[5]int和[10]int是属于不同类型的。⭐:在其他语言中数组大多是引用类......
  • 使用benchmark比较分治法与归纳法求解最大子数组问题的性能
    #include<benchmark/benchmark.h>#include<algorithm>#include<deque>#include<functional>#include<iostream>#include<random>#include<string>#include<vector>usingnamespacestd;staticconstint......
  • 基于贝叶斯判决的手写数字识别系统,带GUI界面
    1.算法描述贝叶斯判别规则是把某特征矢量(x)落入某类集群的条件概率当成分类判别函数(概率判别函数),x落入某集群的条件概率最大的类为X的类别,这种判决规则就是贝叶斯判别规则。贝叶斯判别规则是以错分概率或风险最小为准则的判别规则。判别函数,各个类别的判别区域确定后,可以用......
  • 基于贝叶斯判决的手写数字识别系统,带GUI界面
    1.算法描述      贝叶斯判别规则是把某特征矢量(x)落入某类集群的条件概率当成分类判别函数(概率判别函数),x落入某集群的条件概率最大的类为X的类别,这种判决规则就是贝叶斯判别规则。贝叶斯判别规则是以错分概率或风险最小为准则的判别规则。       判别函数,各个......
  • 染色数组
    定义集合\(S\)由同时满足以下条件的\(x\)构成:\([1,x)\)中\(\lea_{x}\)的元素和\((x,n]\)中\(\gea_{x}\)的元素构成递增子序列\([1,x)\)中\(\gea_{x}\)的元素和\((x,n]\)中\(\lea_{x}\)的元素构成递减子序列性质1:\(a\)为完美数组当且仅当\(S\ne\empty\)必要性:注......
  • 795. 区间子数组个数
    题目描述给一个数组,再给一个值的范围[l,r],问最大值在[l,r]之间的子数组有多少个?f1-双指针基本分析如果枚举子数组的右端点i,会有几种情况?(1)arr[i]>right;(left<=arr[i]<=right;(3)arr[i]<left假如枚举到右端点i,左端点怎么考虑?(1)的情况,这个子数组不满足,可以跳过;(2)......