首页 > 编程语言 > 详细

First Missing Positive leetcode java

时间:2014-08-04 13:34:47      阅读:830      评论:0      收藏:0      [点我收藏+]

题目

 

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.

 

题解

题目给了一个unsorted integer array。当然,可以用先排好序的方法走(但是时间复杂度就不能是O(n))。

所以这里提供一个不先排序的算法。

 

注意:题目要求是find the first missing positive integer

也就是说,即便你给的数组是4 5 6 7,看似都一一排好序,但是返回值一定是1,也就是如果给的数组是4 5 7 8 ,答案不是6,是1。

 

因此,有了这个性质,我们就能i和A[i]是否相等来做判断了。“实现中还需要注意一个细节,就是如果当前的数字所对应的下标已经是对应数字了,那么我们也需要跳过,因为那个位置的数字已经满足要求了,否则会出现一直来回交换的死循环。”引自 Code Ganker

 

代码如下:

 1     private void swap(int[] A, int i, int j){
 2         if(A[i]!=A[j]){
 3             A[i]^=A[j];
 4             A[j]^=A[i];
 5             A[i]^=A[j];
 6         }
 7     }
 8     public int firstMissingPositive(int[] A) {
 9         if(A.length==0||A==null)
10             return 1;
11             
12         for (int i = 0; i < A.length; i++){
13             if (i != A[i]){
14                 if (A[i] <= 0 || A[i] > A.length-1 || A[i] == A[A[i]])
15                     continue;
16                 else{
17                     swap(A, i, A[i]);
18                     i--;
19                 }
20             }
21         }
22         int k = 1;  
23         while (k < A.length && A[k] == k) 
24             k++;  
25             
26         if(A[0]==k)
27             return k+1;
28         else
29             return k;
30     }

 

 

First Missing Positive leetcode java,布布扣,bubuko.com

First Missing Positive leetcode java

原文:http://www.cnblogs.com/springfor/p/3889547.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!