python实现找出数组中丢失的数

微软笔试
题 目 描述:
给定一个由n-1个整数组成的未排序的数组序列，其元素都是1到n中的不同的整数。
请写 出一个寻找数组序列中缺失整数的线性时间算法。

分析与解答:
方法 一 :累加求和
首先分析一下数学性质。 假设缺失的数字是X，那么这n-1个数一定是1~n之间除了X 以外的所有数， 试想一下， l~n一共 n个数的和是可以求出来的，数组中的元素的和也是可 以求出来的， 二者相减， 其值是不是就是缺失的数字 X 的值呢?
为了更好地说明上述方法， 举一个简单的例子。假设数组序列为[2, 1, 4, 5]一共 4 个元 素， n 的值为 5， 要想找出这个缺失的数字，可以首先对 l 到 5 五个数字求和，求和结果为 15 (1+2+3+4+5=15)，而数组元素 的和为 array[O]+array[1]+array[2]+array[3]=2+1+4+5=12， 所 以，缺失的数字为 15一12=3o
通过上面的例子可以很容易形成以下具体思路: 定义两个数 suma 与 sumb， 其中 ， suma 表示的是这 n-1 个数的和， sumb 表示的是这 n 个数的和，很显然，缺失的数字的值即为 sumb-suma 的值。
示例代码如下:

def getNum(arr):
    if arr==None or len(arr)<=0:
        print('参数不合理')
        return -1
    suma=0
    sumb=0
    i=0
    while i<len(arr):
        suma=suma+arr[i]
        sumb=sumb+i
        i+=1
    sumb=sumb+len(arr)+len(arr)+1
    return sumb-suma
if __name__=='__main__':
    arr=[1,4,3,2,7,5]
    print(getNum(arr))
输出：
6

算法性能分析:
方法二:异或法
这种方法的时间复杂度为 O(N)。需要注意的是，在求和 的过程中，计算结果有溢出的可 能性 。 所以，为了避免这种情况的发生，在进行数学运算时，可以考虑位运算，毕竟位运算 性能最好，下面介绍如何用位运算来解决这个问题。
在解决这个问题前， 首先回顾一下异或运算的性质。简单点说，在进行异或运算时， 当 参与运算的两个数相同时，异或结果为假，当参与异或运算的两个数不相同时，异或结果 为真。
实现代码如下 :

def getNum(arr):
    if arr==None or len(arr)<=0:
        print('参数不合理')
        return -1
    a=arr[0]
    b=1
    lens=len(arr)
    i=1
    while i<lens:
        a=a^arr[i]
        i+=1
    i=2
    while i<=lens+1:
        b=b^i
        i+=1
    return a^b
if __name__=='__main__':
    arr=[1,4,3,2,7,5]
    print(getNum(arr))

输出：6

本文地址：https://blog.csdn.net/weixin_42813521/article/details/107657395