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

文章目录

• 前言
• 题目
• 题解
• NO1：哈希表
• NO2：原地数组替换
• 参考文章

前言

哈喽，我是长路，目前刚刚大三，方向是后端也偶尔捣鼓下前端，现在的主语言是Java。之前一大段时间都是在学习web开发的一些技术，就很久没有进行类似于数据结构、算法之类的学习与刷题，打算这段时间拾起来好好学一学、搞一搞。

这段时间也是机缘巧合看到草帽路飞的博客，加了自学群，正巧看到博主组织在群里组织了leetcode刷题打卡活动，我也就参与进来，为期一个月，打算坚持每天都花一些时间做一些题目，并通过博客的方式来进行记录。

目前跟着一个Github仓库刷题(leetcode)：代码随想录leetcode刷题，当前为LeetCode 热题 HOT 100专题。

---

题目

题目来源leetcode

leetcode地址：448. 找到所有数组中消失的数字，难度：简单。

题目描述(摘自leetcode)：

给你一个含 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) 的情况下解决这个问题吗? 你可以假定返回的数组不算在额外空间内。

---

题解

NO1：哈希表

思路：创建一个长度为n的数组，中间存0表示该数字不存在，存1则表示该数字出现过。之后遍历一遍即可求得结果。

代码：时间复杂度O(n)，空间复杂度O(n)

public List<Integer> findDisappearedNumbers(int[] nums) {
    //使用一个数组来进行记录nums中存在的数字
    int[] numArr = new int[nums.length];
    for (int num : nums) {
        numArr[num - 1] = 1;
    }
    //遍历numArr，若是为0则表示不在数组出现的元素
    List<Integer> numList = new ArrayList<>();
    for (int i = 0; i < numArr.length; i++) {
        if (numArr[i] == 0) {
            numList.add(i + 1);
        }
    }
    return numList;
}

---

NO2：原地数组替换

思路：遍历原数组中的元素值，取得该数字-1的值，也就是等会来作为索引的下标，给该索引的值+n来作为该索引数字存在的标记(>n)，之后重新遍历一遍，一旦有某个值<=n，则表示该索引数字+1并没有存在过，即可将空间复杂度优化为O(1)。

代码：时间复杂度O(n)，空间复杂度O(1)

public List<Integer> findDisappearedNumbers(int[] nums) {
    int n = nums.length;
    int x;
    for (int num : nums) {
        x = (num - 1) % n;
        nums[x] += n;
    }
    //重新遍历一遍，若是有数字<n则表示该位置(即数字)没有在原数组汇总出现过
    List<Integer> numList = new ArrayList<>();
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] <= n) {
            numList.add(i + 1);
        }
    }
    return numList;
}

---

参考文章

[1]. leetcode题解

---

我是长路，感谢你的耐心阅读。如有问题请指出，我会积极采纳！ 欢迎关注我的公众号【长路Java】，分享Java学习文章及相关资料 Q群：851968786 我们可以一起探讨学习 注明：转载可，需要附带上文章链接

整理者：长路 时间：2021.11.12