参考内容：万门大学.数据结构与算法进阶（python版本）哔哩哔哩学习视频

一、题目内容

找到丢失的数字：现在你手上有n-1个数字，这些数字的范围是[1,n]，且这n-1个数字中没有重复的数字。有上述条件可知：你手上的数字缺了一个。请编写一段高效的找到缺失数字的代码。

二、题目分析

此题是一道比较老的数据结构与算法考题，首先，在解答该题时，要进行一些题目的分析，题目分析我们主要做些什么呢？
要弄清楚。这n-1个数字是排好序了的吗？
该题有哪些解法思路呢？
要通过分析时间复杂度和空间复杂度说明那种解法最优呢？
最优解法的代码如何实现？
能不能写出测试用例呢？

三、题目解答

1. 排序后使用二分法查找

  1. list.sort()

算法时间复杂度 = 排序的时间复杂度() + 二分查找的时间复杂度（log）
image.png

2. 排序后使用线性查找

算法时间复杂度 = 排序的时间复杂度() + 二分查找的时间复杂度（n）

3. 求和作差法

思路：
sum = 1+2+3+....+n = n(n-1）/2
sum = sum - list[i]
num = sum //最后作差剩下的数

  1. def FindMissingNumber(nums):
  2.     s = 0
  3.     for i in range(0,nums[-1] + 1):
  4.         s = s + i
  5.     for n in nums:
  6.         s = s - n 
  7.     return s 
  9. print(FindMissingNumber([1,3,5,6,4,7]))

image.png

4. 计数排序

有n个抽屉，每个抽屉里面放一个数，最后有空的抽屉就应该装缺失的数。

  1. def FindMissingNumber(nums):
  2.         chouti  = [ 0 for i in range(len(nums)+1)]  # n(列表长度加1)个抽屉里面全为空
  3.         for n in nums:
  4.             chouti[ n-1] = 1                                               # 将数放到对应的抽屉，并标记该抽屉也有数
  5.         return  chouti.index(0)+1                                        # 获取空元素的下标并加1，因为下标是从0开始的
  6. print(FindMissingNumber([1,3,5,6,4,7]))

5. 排序后异或求解

异或的知识：

  1. 相同为0， 不同为1
  2. 0 ^ 0 = 0    ;   
  3. 0 ^ 1 = 1    ;
  4. 1 ^ 0 = 1 ;
  5. 1 ^ 1 = 0 ;
  7. 8 ^ 3 = 1011
  8. 1000
  9. 0011
  10. 1011
  12. A ^ A = 0
  13. A ^ 0 = A 
  14. 1010
  15. 1010 
  16. = 000
  17. 1010
  18. 0000
  19. = 1010 
  20. A ^ B ^ C ^ D = 0 //表示二进制数最后一位1的个数为偶数

有了上面的思想， 我们可以将n-1 个数
a```` , a```` .... ，a````
1, 2 ， .... ， n
进行逐位异或，最后选出异或结果不为0的数。

  1. def FindMissingNumber(nums):
  2.     new_nums = sorted(nums)
  3.     n = len(new_nums)
  4.     for i in range(1,n+2):
  5.         if i^ new_nums[i-1] != 0:
  6.             return i
  7.             break
  8. print(FindMissingNumber([1,3,5,6,4,7]))