【排序】268. 丢失的数字

标签：268 return nums max len 排序 total 丢失

链接 https://leetcode.cn/problems/missing-number/submissions/

 

思路一：

直接排序，排序后遍历，发现元素跟下标不同就返回下标即可。

如果遍历到最后都没有返回，说明是最后一个数字不见了，直接返回数组的长度就可以了。

.

思路二：

线性时间，常数空间。这样的话排序肯定是不行的。排序最快也就是nlogn。所以这种情况一般是只能借助于数学公式。

我们发现，这个题目就是一个等差数列，我们计算出来一个和，然后遍历这个数组，减去每一个元素，剩下的值就是我们要找的元素了。

 

思路一代码：

1 class Solution:
2     def missingNumber(self, nums) -> int:
3         nums.sort()
4         for i in range(len(nums)):
5             if i != nums[i]:
6                 return i
7         return len(nums)

思路二代码：

1 class Solution:
2     def missingNumber(self, nums) -> int:
3         max_len = len(nums)
4         total = (1 + max_len) * max_len // 2
5         for i in nums:
6             total -= i
7         return total

 

标签：268,return,nums,max,len,排序,total,丢失
From： https://www.cnblogs.com/bjfu-vth/p/16757085.html