题目大意:
给你一个含 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等统计方式轻而易举的可以写出代码。本文我们来重点分析如何不使用额外存储空间,即空间复杂度在O(1)的情况下解决问题。
首先观察题目给出的数组,如果我们能把每个数字放到它该出现的位置,那么所有没有出现数字的位置就是缺失的部分。操作上我们可以这样:从数组首位开始向后循环,计算当前数字应该出现的位置,比如数字1,应该放在下标为0的地方,数字5则是应放在下标4的位置。总结来说,数字n应该出现在数组下标为n-1处。接下来我们交换当前下标与该数字应位于下标位置的数字,交换后,当前数字处于正确的位置,而被交换到当前位置的数字可能仍然是错误的位置,因此我们需要继续对当前位置进行判断。如果当前位置的数字与被交换位置的数字相同时,我们则不需要交换(数字相同,交换也没有意义),此时循环下标加一,继续重复上述操作。出现这种2个位置数字相同的原因有两种情况:1. 数组中存在相同数字,被交换位置上的数字是之前操作时交换到该位置的正确数字,或者该位置上原本就是正确的数字。2. 当前下标和被交换下标相同,也就是说当前数字处于正确位置上。
整理好数组后,我们再循环一遍数组,如果当前位置的数字与下标加一不相同的话,那么当前位置上就是缺失的数字。
实现代码:
class Solution { public List<Integer> findDisappearedNumbers(int[] nums) { List<Integer> res = new ArrayList(); // 返回结果 for(int i=0;i<nums.length;){ // 循环数组,整理数组 int realIndex = nums[i] -1; // 当前数字应出现在的正确位置 if(nums[i] == nums[realIndex]){ // 如果正确位置上的数字与当前数字相同 // 无需交换数字,循环至数组下一位置。 i++; continue; } // 交换两个位置上的数字。 // 下面是使用亦或位运算方法交换两个数字,这样不会使用额外存储空间 nums[i]^=nums[realIndex]; nums[realIndex]^=nums[i]; nums[i]^=nums[realIndex]; } // 寻找缺失的部分 for(int i=0;i<nums.length;i++){ if(nums[i] != i+1){ res.add(i+1); } } return res; } }
本题解法执行时间为5ms。
Runtime: 5 ms, faster than 81.82% of Java online submissions for Find All Numbers Disappeared in an Array.Memory Usage: 48 MB, less than 71.65% of Java online submissions for Find All Numbers Disappeared in an Array.
本网站文章均为原创内容,并可随意转载,但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: https://leetcode.jp/leetcode-448-找到所有数组中消失的数字-解题思路分析/