LC.P268[丢失的数字]

LC.P268[丢失的数字]

方法一：哈希表

class Solution {
    public int missingNumber(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) set.add(num);
        int n = nums.length;
        for (int i = 0; i <= nums.length; ++i) {
            if (!set.contains(i)) return i;
        }
        return n;
    }
}

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

方法二：排序

class Solution {
    public int missingNumber(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            if (i != nums[i]) return i;
        }
        return n;
    }
}

• 时间复杂度：$O(nlogn)$
• 空间复杂度：$O(logn)$

方法三：数学

class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        int cur = 0, sum = n * (n + 1) / 2;
        for (int num : nums) cur += num;
        return sum - cur;
    }
}

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

方法四：位运算

class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length, ans = n;
        for (int i = 0; i < n; ++i) {
            ans ^= nums[i] ^ i;
        }
        return ans;
    }
}

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$