原题如下:
Given an unsorted integer array, find the first missing positive integer.
For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.
Your algorithm should run in O(n) time and uses constant space.
题目要求找出第一个缺失的正整数,难点在于时间复杂度要控制在O(n),也就是说不能对数组排序,空间复杂度要控制在O(1),也就是说不能开一个新的数组去存储这些数字。
但是这道题目也有它的特点,假如给定的数组的长度为n,那么缺失的第一个正数肯定在[1,n+1]内,根据这个特点,可以将范围为[1,n]的数字移动到与其数值相等的下标的位置,对所有的数这样操作后从头遍历一遍数组,找出的第一个 i+1 != a[i]
的i,那么i+1就是第一个缺失的正整数。
1 | class Solution(object): |