【Python】第一个缺失的整数

超、凢脫俗 2022-05-22 08:25 166阅读 0赞

# 第一个缺失的整数 #

> 给定一个数组A\[0…N-1\]，找到从1开始，第一个不在数组中的正整数。  
> 如3,5,1,2,-3,7,14,8输出4

## 循环不变式 ##

思路：将找到的元素放到正确的位置上，如果最终发现某个元素一直没有找到，则该元素即为所求。  
循环不变式：如果某命题初始为真，且每次更改后仍然保持该命题为真，则若干次更改后该命题仍然为真。  
为表述方便，下面的算法描述从1开始数

## 利用循环不变式设计算法 ##

假定前i-1个数已经找到，并且依次存放在A\[1,2,…,i-1\]中，继续考察A\[i\]：  
若A\[i\]＜i且A\[i\]≥1，则A\[i\]在A\[1,2,…,i-1\]中已经出现过，可以直接丢弃。  
若A\[i\]为负，则更应该丢弃它。  
若A\[i\]＞i且A\[i\]≤N，则A\[i\]应该位于后面的位置上，则将A\[A\[i\]\]和A\[i\]交换。  
若A\[i\]≥N，由于缺失数据一定小于N，则A\[i\]丢弃。  
若A\[i\]＝i，则A\[i\]位于正确的位置上，则i加1，循环不变式扩大，继续比较后面的元素

## 合并相同的分支 ##

整理算法描述：  
若A\[i\]＜i或者A\[i\]＞N，则丢弃A\[i\]  
若A\[i\]＞i，则将A\[A\[i\]\]和A\[i\]交换。  
若A\[i\]＝i，i加1，继续比较后面的元素。  
思考：如何快速丢弃A\[i\]？  
将A\[N\]赋值给A\[i\]，然后N减1。

## Python代码 ##

def first_missing_number(li):
        size = len(li)
        li.insert(0, None)  # 为了方便从1开始数，在数组前面添加None占位
        i = 1
        while i <= size:
            if li[i] < i or li[i] > size:
                li[i] = li[size]
                size -= 1
            elif li[i] > i:
                # 交换
                temp = li[i]
                li[i] = li[temp]
                li[temp] = temp
            else:
                i += 1
        return i
    
    
    if __name__ == '__main__':
        li = [3, 5, 1, 2, -3, 7, 14, 8]
        result = first_missing_number(li)
        print(result)

输出结果：4

参考七月在线