网站开发的有关公司,四川建设网上班时间,广州网站制作方法,网上销售培训课程给你一个含 n 个整数的数组 nums #xff0c;其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字#xff0c;并以数组的形式返回结果。 官解#xff1a; 方法一#xff1a;原地修改 思路及解法 我们可以用一个哈希表记录数组 nums 中…给你一个含 n 个整数的数组 nums 其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字并以数组的形式返回结果。 官解 方法一原地修改 思路及解法 我们可以用一个哈希表记录数组 nums 中的数字由于数字范围均在[1,n] 中记录数字后我们再利用哈希表检查[1,n] 中的每一个数是否出现从而找到缺失的数字。 由于数字范围均在 [1,n]中我们也可以用一个长度为n 的数组来代替哈希表。这一做法的空间复杂度是 O(n) 的。我们的目标是优化空间复杂度到O(1)。 注意到nums 的长度恰好也为 n能否让nums 充当哈希表呢 由于nums 的数字范围均在[1,n] 中我们可以利用这一范围之外的数字来表达「是否存在」的含义。 具体来说遍历nums每遇到一个数 x就让 nums[x−1] 增加 n。由于 nums 中所有数均在 [1,n] 中增加以后这些数必然大于 n。最后我们遍历 nums若 nums[i] 未大于 n就说明没有遇到过数i1。这样我们就找到了缺失的数字。 注意当我们遍历到某个位置时其中的数可能已经被增加过因此需要对 n 取模来还原出它本来的值。 class Solution {public ListInteger findDisappearedNumbers(int[] nums) {int n nums.length;for(int num : nums){//计算出它真实的位置int x (num - 1) % n;//真实的位置上的数字你数组的长度nums[x] n;} //创建返回结果的数组ListInteger ret new ArrayListInteger();//遍历for(int i 0;i n;i){//当前数组的数值小于数组长度就说明没有这个数字if(nums[i] n){//就把这个数添加在数组中为什么1因为i是下标下标从0开始ret.add(i1);}}return ret;}
}
