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

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

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

题解一：使用额外空间进行桶排序

就是定义一个数组a，初始值为0，下标为i时，a[i]++；nums[i]为0，说明i没出现过

题解二：原地修改（进阶）

“数组元素-1”变为新下标，新下标对应的元素修改掉，没被修改的下标就是消失的数

class Solution { public List findDisappearedNumbers(int[] nums) { int n=nums.length; for(int num : nums){ num =(num-1)%n;//对n取模来还原本来的值，这是为什么？ nums[num]+=n; } List result =new ArrayList();//ArrayList的L一定要大写 for(int i=0;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。