pythontip 100days-day38

题目

有一组数字，从1到n，中减少了一个数，顺序也被打乱，放在一个n-1的数组里，请找出丢失的数字

例子

find_missing_num([1,2,3,5]) -> 4

假设

1. 输入的数组不为空，且一定符合题意

tips

1. 位运算

答案

解法1

def find_missing_num(lst):
    res = 0
    for i in range(1, len(lst)+1):
        res ^= i

    for item in lst:
        res ^= item

    return res

性能：

1. 时间复杂度O(n)
2. 空间复杂度O(1)

关键点：

1. 位运算