本文共 1663 字,大约阅读时间需要 5 分钟。
转自
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.
虽然不能再另外开辟非常数级的额外空间,但是可以在输入数组上就地进行swap操作。
思路:交换数组元素,使得数组中第i位存放数值(i+1)。最后遍历数组,寻找第一个不符合此要求的元素,返回其下标。整个过程需要遍历两次数组,复杂度为O(n)。
下图以题目中给出的第二个例子为例,讲解操作过程。
n个元素的数组,里面的数都是0~n-1范围内的,求数组中重复的某一个元素,没有返回-1, 要求时间性能O(n) 空间性能O(1)。
python代码:
class Solution(object): def firstMissingPositive(self, nums): """ :type nums: List[int] :rtype: int """ if nums == None or len(nums) == 0: return 1 length = len(nums) pos = 0 while pos < length: if nums[pos] >= 1 and nums[pos] != pos + 1 and nums[pos] <= length and nums[pos] != nums[nums[pos] - 1]: self.swap(nums, pos, nums[pos] - 1) else: pos += 1 for i in range(length): if nums[i] != i + 1: return i + 1 return length + 1 def swap(self, nums, pos, nums_pos): temp = nums[pos] nums[pos] = nums[nums_pos] nums[nums_pos] = temp
转载地址:http://fmbvb.baihongyu.com/