本文共 2104 字,大约阅读时间需要 7 分钟。
题目链接:
Given an unsorted integer array, find the smallest missing positive integer.
Example 1:
Input: [1,2,0]Output: 3
Example 2:
Input: [3,4,-1,1]Output: 2
Example 3:
Input: [7,8,9,11,12]Output: 1
Note:
Your algorithm should run in O ( n ) O(n) O(n) time and uses constant extra space.给出一个无序的int
类型数组,要求出其缺失的最小正整数。要求时间复杂度为 O ( n ) O(n) O(n)。并且需要的额外空间只能是常量大小。
hard
了。 不符合要求的解法:
正确的解法:
在常量大小的额外空间时,排序算法的时间复杂度最小为 O ( n ∗ l o g n ) O(n*logn) O(n∗logn),因此,不能使用排序算法。 要达到时间复杂度为 O ( n ) O(n) O(n)的要求,这意味着我们只能对该数组进行少量次数的遍历。注意到题目要求的是找出缺失的最小正整数。假如没有重复的数,并且数组已经排好序了。如果没有缺失的数,那么第i
个元素的值应该是i + 1
(因为0
不属于正整数);那么最小缺失的正整数,应该是第一个nums[i]
不等于i + 1
本来应该的值,即i + 1
。如果没有缺失,那么就是nums.length + 1
。
那么,对于不符合要求的数应该放置再哪里呢?注意到一个事实,如果第i
个元素不符合要求,那么之后的元素如何放置都没有关系(因为我们找的是第一个不符合要求的)。
所以我们可以从右到左遍历整个数组,对于第j
个元素
j + 1
,则说明当前元素不符合要求,继续向左遍历(j--
)。j + 1
,说明该位置放对了,不需要改变,也是继续向左遍历。temp
大于0
并且小于j + 1
。那么他应该被放置到nums[temp - 1]
的位置,然后将当前元素的值置为nums[temp - 1]
原本的值。如果考虑到有重复的元素,即nums[temp - 1]
原来的值为temp
(已经正确放置),此时也不需要改变当前元素的值,继续向左遍历即可。nums[j] != j + 1
的位置,然后返回j + 1
即可。如果都符合,返回nums.length + 1
。对于这种解法,总共需要遍历两遍,在第一次遍历的时候,有可能对于某个位置j
,需要替换前面所有的元素(替换j - 1
次,最差情况,这时总共需要遍历3遍,但时间复杂度也是 O ( n ) O(n) O(n))。时间复杂度为 O ( n ) O(n) O(n)。替换时均在原来的数组上进行,空间复杂度为 O ( 1 ) O(1) O(1)。符合题目要求。
class Solution { public int firstMissingPositive(int[] nums) { int temp = 0; int j = nums.length - 1; while (j >= 0) { temp = nums[j]; // 如果没有缺失,第 j 个位置的值应该是 j + 1 if (temp <= 0 || temp >= j + 1) { // 该位置的值符合要求或者是超出范围 j--; } else if (nums[temp - 1] == temp) { // 有重复元素 j--; } else { // 将 nums[j] 放到正确的位置 nums[j] = nums[temp - 1]; nums[temp - 1] = temp; } } // 寻找不符合要求的位置 for (j = 0; j < nums.length; j++) { if (nums[j] != j + 1) { return j + 1; } } return j + 1; }}
转载地址:http://bibmb.baihongyu.com/