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-找到所有数组中消失的数字-解题思路分析/