题目链接 : https://leetcode-cn.com/problems/first-missing-positive/
题目描述:
给定一个未排序的整数数组，找出其中没有出现的最小的正整数。
示例:
示例 1:
输入: [1,2,0]
输出: 3
示例 2:
输入: [3,4,-1,1]
输出: 2
示例 3:
输入: [7,8,9,11,12]
输出: 1
说明:
你的算法的时间复杂度应为(O(*n*))，并且只能使用常数级别的空间。
思路:
本来想用集合,直接有
def firstMissingPositive(self, nums: List[int]) -> int:
i = 1
nums = set(nums)
while i in nums:
i += 1
return i
这也太简单了吧,根本配不上困难题啊!
再看题目要求,对空间复杂度,时间复杂度都有要求.虽然集合做法时间复杂度低,但是能说不过去吗? 这明显不是用了 (O(n))空间 ,哈哈.
还可以排序的,这个时间复杂度又不行!
怎么办呢?再看题目中有提示:
- 想想如何在非恒定空间中解决问题,你能将这种逻辑应用到现有空间吗?
- 我们不关心重复或非正整数
- 记住(O(2n)= O(n))
有几个重点,1. 现有空间 2. 要扫数组两次.
所以,这里我们有个小技巧,把数组的索引号利用起来,如果我们把位置0我们放数字1,位置1我们放数字2...我们就可以节省存储索引的空间了,按照这样的方法重新整理数组,我们再扫一次就能知道答案了.
比如示例中的:[3,4,-1,1]
第一步,数字3它应该放在位置2 ,交换位置,[-1,4,3,1]
第二步,数字4应该放在位置3,交换位置,[-1,1,3,4],此时有个关键,数字1应该在位置0,所以我们继续交换,[1,-1,3,4]
...
我们再次扫数组,就能得到结果.
所以,时间复杂度:(O(2n)),空间复杂度:(O(1))
关注我的知乎专栏,了解更多的解题技巧,大家共同进步!
代码:
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
n = len(nums)
for i in range(n):
while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
#print(nums)
i = 0
while i < n and i + 1 == nums[i]:
i += 1
return i + 1
class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;
for (int i = 0; i < n; i++) {
while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
swap(nums, nums[i] - 1, i);
}
}
int i = 0;
while (i < n && i + 1 == nums[i]) i++;
return i + 1;
}
private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}