268. 丟失的數字

難度：簡單

題目

給定一個包含 [0, n] 中 n 個數的數組 nums ，找出 [0, n] 這個范圍內沒有出現在數組中的那個數。

示例 1：

輸入：nums = [3,0,1]
輸出：2
解釋：n = 3，因為有 3 個數字，所以所有的數字都在范圍 [0,3] 內。2 是丟失的數字，因為它沒有出現在 nums 中。

示例 2：

輸入：nums = [0,1]
輸出：2
解釋：n = 2，因為有 2 個數字，所以所有的數字都在范圍 [0,2] 內。2 是丟失的數字，因為它沒有出現在 nums 中。

示例 3：

輸入：nums = [9,6,4,2,3,5,7,0,1]
輸出：8
解釋：n = 9，因為有 9 個數字，所以所有的數字都在范圍 [0,9] 內。8 是丟失的數字，因為它沒有出現在 nums 中。

示例 4：

輸入：nums = [0]
輸出：1
解釋：n = 1，因為有 1 個數字，所以所有的數字都在范圍 [0,1] 內。1 是丟失的數字，因為它沒有出現在 nums 中。

提示：

• n == nums.length
• 1 <= n <= 10^4
• 0 <= nums[i] <= n
• nums 中的所有數字都 獨一無二

進階：你能否實現線性時間復雜度、僅使用額外常數空間的算法解決此問題?

個人題解

方法一：異或運算

異或性質：

0 ^ n = n

n ^ n = 0

思路：

1. 由題獨一無二可知，利用異或運算的性質即可求出這里面沒有的數
2. 即定義一個變量初始為0，將 0~n 的所有數與該變量異或，然后再與數組中所有數異或，最后的結果便是丟失的數字

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

復雜度分析

• 時間復雜度：O(n)
• 空間復雜度：O(1)

官方題解

方法一：排序

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

復雜度分析

• 時間復雜度：O(n logn)
• 空間復雜度：O(1)

方法二：哈希集合

首先遍歷數組 nums ，將數組中的每個元素加入哈希集合，然后依次檢查從 0 到 n 的每個整數是否在哈希集合中，不在哈希集合中的數字即為丟失的數字。由于哈希集合的每次添加元素和查找元素的時間復雜度都是 O(1) ，因此總時間復雜度是 O(n)

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

復雜度分析

• 時間復雜度：O(n)
• 空間復雜度：O(n)

方法三：位運算

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

復雜度分析

• 時間復雜度：O(n)
• 空間復雜度：O(1)

方法四：數學

將從 0 到 n 的全部整數之和記為 total，根據高斯求和公式 total = (n * (n+1)) / 2

將數組 nums 的元素之和記為 arrSum，則 arrSum 比 total 少了丟失的一個數字，因此丟失的數字即為 total 于 arrSum 之差。

class Solution {public int missingNumber(int[] nums) {int n = nums.length;int total = n * (n + 1) / 2;int arrSum = 0;for (int i = 0; i < n; i++) {arrSum += nums[i];}return total - arrSum;}
}

復雜度分析

• 時間復雜度：O(n)
• 空間復雜度：O(1)

作者：力扣官方題解
鏈接：https://leetcode.cn/problems/missing-number/solutions/1085105/diu-shi-de-shu-zi-by-leetcode-solution-naow/
來源：力扣（LeetCode）
著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。