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.length1 <= n <= 1040 <= nums[i] <= nnums中的所有数字都独一无二
方法一：排序
将数组排序之后，即可根据数组中每个下标处的元素是否和下标相等，得到丢失的数字。
由于数组的长度是 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;}};javaclass 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;}}pythonclass 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;}};
