首页 > 代码库 > [leetcode]First Missing Positive

[leetcode]First Missing Positive

2024-07-16 16:55:11   216人阅读

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.

算法分析：

将1 ~ a.length的数字放到与下标相应的位置，其他的复数或者大于a.length的不作处理。

然后再次遍历a，找到第一个缺省的整数

【注意】重复数字、负数的处理；i应该放在i - 1的位置，但是如果i - 1位置放的也是i，跳过；非正数跳过；太大的数字跳过；

代码如下：

 1 public class Solution { 2     public int firstMissingPositive(int[] a) { 3         if(a == null || a.length == 0) return 1; 4         int length = a.length; 5         for(int i = 0; i < length; i++){ 6             if(a[i] > length - 1 || a[i] <= 0 || a[i] == a[a[i] - 1]) continue; 7             int t = a[a[i] - 1]; 8             a[a[i] - 1] = a[i]; 9             a[i] = t;10             i--;11         }12         int positive = 1;13         for(int i = 0; i < length; i++){14             if(a[i] <= 0) continue;15             if(a[i] == positive){16                 positive++;17             }else{18                 return positive;19             }20         }21         return positive;22     }23 }

这道题出的很好。

 


联系
我们