LEETCODE 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等统计方式轻而易举的可以写出代码。本文我们来重点分析如何不使用额外存储空间,即空间复杂度在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.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-448-找到所有数组中消失的数字-解题思路分析/
此条目发表在leetcode分类目录,贴了, 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。