https://leetcode-cn.com/problems/first-missing-positive/
# -*- coding:utf-8 -*- class Solution(object): def firstMissingPositive(self, nums): """ :type nums: List[int] :rtype: int """ n = len(nums) temp_list = [0 for _ in range(n)] for each in nums: if each <= n and each > 0: temp_list[each - 1] = each for i in range(n): if temp_list[i] != i + 1: return i + 1 return n + 1 if __name__ == '__main__': nums = [1] print(Solution().firstMissingPositive(nums))
思路:这道题首先生成一个长度为n的列表,然后遍历整个数组,将>0并且<n的数字放入列表中,如果有位置为初始值0,则说明缺少这个,如果列表没有缺失位置,则说明缺失值为n+1。
这个方法空间和时间复杂度都为O(n)。但是题里说线性空间,那么我们可以提前遍历一遍数组,求出正数和个数,这样就可以把n缩小,空间复杂度也将为了常数。
这是典型的时间换空间的做法,实际上不做处理也可以达到一个很好的效果。

0 条评论