268. 丢失的数字

难度简单512

给定一个包含 [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 <= 104
• 0 <= nums[i] <= n
• nums 中的所有数字都 独一无二

  方法一：排序
  将数组排序之后，即可根据数组中每个下标处的元素是否和下标相等，得到丢失的数字。

  由于数组的长度是 nn，因此下标范围是 [0, n-1][0,n−1]。假设缺失的数字是 kk，分别考虑以下两种情况：

  当 0 \le k < n0≤k<n 时，对任意 0 \le i < k0≤i<k，都有 \textit{nums}[i]=inums[i]=i，由于 kk 缺失，因此 \textit{nums}[k]=k+1nums[k]=k+1，kk 是第一个满足下标和元素不相等的下标；

  当 k = nk=n 时，00 到 n-1n−1 都没有缺失，因此对任意 0 \le i < n0≤i<n，都有 \textit{nums}[i]=inums[i]=i。

  根据上述两种情况，可以得到如下方法得到丢失的数字：

  从左到右遍历数组 \textit{nums}nums，如果存在 0 \le i < n0≤i<n 使得 \textit{nums}[i] \ne inums[i] 
  
  ​
   =i，则缺失的数字是满足 \textit{nums}[i] \ne inums[i] 
  
  ​
   =i 的最小的 ii；

  如果对任意 0 \le i < n0≤i<n，都有 \textit{nums}[i]=inums[i]=i，则缺失的数字是 nn。

  class Solution {
  public:int missingNumber(vector<int>& nums) {sort(nums.begin(),nums.end());int n = nums.size();for (int i = 0; i < n; i++) {if (nums[i] != i) {return i;}}return n;}
  };java
  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;}
  }python
  class Solution:def missingNumber(self, nums: List[int]) -> int:nums.sort()for i, num in enumerate(nums):if num != i:return ireturn len(nums)

• 

• class Solution {
  public:int missingNumber(vector<int>& nums) {unordered_set<int> set;int n = nums.size();for (int i = 0; i < n; i++) {set.insert(nums[i]);}int missing = -1;for (int i = 0; i <= n; i++) {if (!set.count(i)) {missing = i;break;}}return missing;}
  };