现在的位置: 首页 > 综合 > 正文

LeetCode OJ –问题与解答 First Missing Positive

2014年04月05日 ⁄ 综合 ⁄ 共 1353字 ⁄ 字号 评论关闭

题目


Given an unsorted integer array, find the first missing positive integer.

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.

给定未排序的数字序列,找出最小的未出现的正数;0不算正数,O(n)时间完成,不能额外空间。

思路


说到未排序,首先想到排序~ 排序好后从头到尾检查,能够完成解答,但是所有比较排序至少O(nlgn);桶排序,计数排序啥的的确O(n),可是需要额外的空间。看来此路不通。
考虑了下需要的变量:数组的总数(这样最大的n就可以知道,有),数组元素(有),从1-n每次要比较的自然数(可以有,但是没办法一直存储,或者说每次都要从头到尾扫一遍数组),看来问题出在这里。山重水复疑无路之时,想到数组本身的下标就是一个很好的记录点。好!
对应的数放到对应的索引上,例如1放到A[1]上,这样只需要O(n)的遍历就能完成,然后用一个O(n)的遍历找第一个没有放到索引上的数返回。

细细想来,其实就是桶排序的部分内容,只是没有找额外的桶。


代码



public class Solution {
    public int firstMissingPositive(int[] A) {
        if(A==null){
            return 1;
        }
        if(A.length == 0){
            return 1;
        }
        int n = A.length;
        for(int i =0;i<n;i++){
            if(A[i]>=0&&A[i]<n&&A[A[i]]!=A[i]){
                int temp =A[i];
                A[i]=A[A[i]];
                A[temp]=temp;
                i--;
                
            }
            
        }
        for(int i=1;i<n;i++){
            if(A[i]!=i){
                return i;
            }
        }
        return A[0]==n?n+1:n;
    }
}


细节


1 极限情况,a 是null的时候,应该抛出异常;a 没有元素的时候,缺的就是1;这里就都写成1 ,还是通过了。

2.1 循环里面只有一个判断条件,就是 i 时,元素A[i]=j(作为下标),A[j]的内容是否和j一样。不一样就换到合适的位子。这样所有j都放到合适的位子了。

2.2 注意,j需要再0~n-1之中,不然就不去管它,而且必须放在开头检查。因为之后就要作为下标了

3 交换的时候 最后一行 a[temp]=temp是很重要的。如果写成 a[a[i]]=a[i]是有问题的,理解其中的不同含义。

4 i-- 代表被交换过来的元素未必检查过,需要重新检查一下。

5 如果能够检查到最后,个么A[0]要么等于n,要么不等于。


测试


1 极限情况 a=null a = [] 

2 一般情况 a =[3,1,5,6,7,4]

3 数字出现重复的情况 a=[2,2,1,1] [1,2,1,2]

4 数字出现负数的情况  [1,-3,5,10] [-1,1,2,4] [-1,-2,-3]

5 数字出现大数的情况  [100,99,1,2] [100,99,98,97]


PS:

1 大年初二,其实做题目了,但是没有写上来,所以今天会发两篇。

2 以后写的方式就是 1题目 2思路 3 代码 4 细节 5 测试

3 csdn发博客的分割线我没有找到,目前都是复制黏贴格式来写。有没有看到的大牛帮助一下,谢谢啊?


抱歉!评论已关闭.