leetCode-268:Missing Number

问题描述

给定一个长度为 n 的非负整数数组，数组中元素均不相同，且元素都是 [0, n] 之间的某个数，要求找出数组中不在 [0, n] 中的数字。题目链接：点我

样例输入输出

输入：nums = [3,0,1]

输出：2

解释：数组长度为 3，所以元素范围为 [0, 3]，数组中只有元素 0、1、3，缺少 2，所以返回 2

输入：nums = [0, 1, 2]

输出：3

解释：数组长度为 3，所以元素范围为 [0, 3]，数组中只有元素 0、1、2，缺少 3，所以返回 3

问题解法

此题比较简单的做法是排序后遍历取出缺少的值，这样时间复杂度是 O(nlogn)，另一种降低时间复杂度的做法是使用 set 保存数组元素，然后遍历找出缺失的元素，这样时间复杂度是 O(n)，空间复杂度是 O(n)，再优化点的做法是使用原地哈希方式，将数组元素依次映射到正确位置上，然后遍历数组找出缺失的元素，这样时间复杂度是 O(n)，空间复杂度是 O(1)。代码如下

class Solution {
    public int missingNumber(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            while (nums[i] != nums.length && nums[i] != i) {
                int temp = nums[i];
                nums[i] = nums[temp];
                nums[temp] = temp;
            }
        }

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i) {
                return i;
            }
        }

        return nums.length;
    }
}