您现在的位置是:首页 > 正文

【NO.90】LeetCode HOT 100—448. 找到所有数组中消失的数字

2024-02-29 13:33:58阅读 3

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

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

1 <= nums[i] <= n

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

解题

方式一:哈希表

判断某个数是否存在,立马想到的就是哈希表,所以我们可以用hashmap保存出现的数的次数,然后遍历整个哈希表,哪一个key对应的value为0,那这个数就是我们要找的。

 /**
 * 时间复杂度:O(n) 
 * 空间复杂度:O(n),用到了哈希表
 */
class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        int n = nums.length;
        List<Integer> result = new ArrayList<>();
        // 哈希表
        HashMap<Integer, Integer> map = new HashMap<>();
        // 初始化
        for (int i = 1; i <= n; i++) {
            map.put(i, 0);
        }
        // 统计次数
        for (int i = 0; i < n; i ++) {
            if (map.containsKey(nums[i])) {
                map.put(nums[i], map.get(nums[i]) + 1);
            }
        }
        // 找出答案
        for (int key : map.keySet()) {
            if (map.get(key) == 0) {
                result.add(key);
            }
        }return result;
    }
}

方式二:原地修改(不使用哈希表)

在方式一的基础上,我们可以用另一种方式代替哈希表,我们可以原地修改给定的nums数组。找到[1, n] 在数组中对应下标[0,n-1]的数, 将其+n,最终数组里<=n 的数,其对应的下标+1 就是那个没有出现的数。

/**
 * 时间复杂度:O(n) 
 * 空间复杂度:O(1)
 */
class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        // 找到[1, n] 在数组中对应下标[0,n-1]的 数, 将其+n,最终数组里<=n,其对应的下标+1 就是那个没有出现的数
        int n = nums.length;
        for (int num : nums) {
            // 此x就是转化后的下标
            int x = (num - 1) % n;
            nums[x] += n;
        }List<Integer> result = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (nums[i] <= n) {
                // 假如这个值<=n,其对应的下标+1 就是那个没有出现的数
                result.add(i + 1);
            }
        }return result;
    }
}

网站文章

  • '\b'退格符号笔记

      今天在给小孩儿讲for循环输出最后一个输出项没有空格的情况  借助标记,选择在第二个至最后一个的输出项前添加空格1 int flag = 0;2 for(int i = 0; i < n; i++) {3 if(flag == 0) cout << a[i];4 else cout << ' ' << ...

    2024-02-29 13:33:51
  • Python多线程获取小米应用商店App,看看我是怎么做到的(干货篇)

    Python多线程获取小米应用商店App,看看我是怎么做到的(干货篇)

    一、【项目背景】小米应用商店给用户发现最好的安卓应用和游戏,安全可靠,可是要下载东西要一个一个的搜索太麻烦了。而且速度并不是很快。今天小编就教大家利用多线程爬取小米应用商店的游戏模块,快速获取我们想要...

    2024-02-29 13:33:45
  • 特检院计算机网络需求分析,呼伦贝尔市特检所开展质量管理体系文件宣贯培训工作-体系文件...

    3月4日呼伦贝尔市特种设备检验所质量管理体系文件宣贯培训班如期举行。此次宣贯培训是该所2016年工作计划安排中的一项重要内容,所领导班子成员、各检验业务科室和综合管理科室人员参加了学习。此次培训内容是...

    2024-02-29 13:33:15
  • Numpy教程

    Numpy教程

    前言参见:What is NumpyNumpy是Python科学计算的基本包,它提供一个多维数组对象及各种派生对象(如屏蔽的数组和矩阵)以及一系列用于数组快速操作的例程,包括数学、逻辑、形状操作、排序...

    2024-02-29 13:33:08
  • 深入理解计算机系统------第八章fork函数运用

    深入理解计算机系统------第八章fork函数运用

    近期学到了深入理解计算机系统基础第八章异常控制流,接下来说一说在这一章C位出道的fork()函数吧。 fork函数 父进程通过调用fork函数来创建一个新的运行的子进程。 #include #include pid_t fork(void); 返回:子进程返回0,父进程返回子进程的PID,如果创建出错,返回-...

    2024-02-29 13:33:01
  • GrapeCity Documents for Excel, .NET Crack

    GrapeCity Documents for Excel, .NET Crack

    在.NET、.NET Core、.NET Framework、Mono、Xamarin.iOS和Xamarin.Android的应用程序中使用。基于Excel的文档对象模型-基于接口的API允许您导入...

    2024-02-29 13:32:55
  • maven指令

    (1)打包的时候去掉test测试代码:mvn clean install -Dmaven.test.skip

    2024-02-29 13:32:25
  • uni-app开发教程之swiper组件使用教程

    uni-app开发教程之swiper组件使用教程

    Uniapp是一款跨平台的开发框架,可以用于开发微信小程序、H5、App等多种应用。其中,swiper组件是一种非常常用的组件,可以实现轮播图、图片滑动等效果。本文将详细介绍如何在Uniapp中使用swiper组件。

    2024-02-29 13:32:18
  • 深度学习概念合集(二)

    深度学习概念合集(二)

    56层比20层要错误要高很多,那多的36层怎么搞,需要来进行同等映射,不能剔除,那就把有用的层保持,无用的层权重参数变成0。感受野的定义是卷积神经网络每一层输出的特征图(feature map)上的像...

    2024-02-29 13:32:10
  • [转载]实用而有效的美剧英文学习法

    [转载]实用而有效的美剧英文学习法

    如果没有英语学习资料你是否可以自己学习好英语?答案是肯定的,看英文美剧就是一个不错的英语学习方法,虽然这样在学习时间上有些长久,但是是在兴趣中学习,同样会有所提高的。那么如何通过美剧学习英语呢,一起来了解下吧。  1、学会选择适合自己的美剧      >>>最新英语教材免费大赠送  非常有特点或专业性的美剧,比如《越狱》《豪斯医生》《越狱》等,可以作为学习补充,但最好不要把它们

    2024-02-29 13:31:42