First Missing Positive

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.把数组中有可能是答案的数([1,n+1]闭区间内的数)放在正确的位置上：num放在下标为num-1的位置上，比如4放在下标为3的位置上，注意有可能是答案的数才放，此时不会数组越界。
2.最后在这些可能的位置上找答案，这些位置是0到n-1。
举几个例子：
[5,6,7],答案：1
[5]，答案：1
[-5],答案：1
[0]，答案：1
[1]，答案：2
[2,2]，答案：1
注意最后这个例子，对于第一个2，这个数在答案区间内，可是我们发现在他应该出现的位置上已经是他了，那么我们视当前这个位置的2不是答案，跳过这个。这个特例需要注意哟~

注意

注意[2,2]这种情况哟

代码

public class Solution {
public int firstMissingPositive(int[] nums) {
for (int i = 0; i = 1 && n

关键字：leetcode, nums, 答案, int

版权声明

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处。如若内容有涉嫌抄袭侵权/违法违规/事实不符，请点击 举报 进行投诉反馈！