首页 > 代码库 > First Missing Positive

First Missing Positive

2024-07-04 07:17:01   230人阅读

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.

开始没有想到这个思路，参考网上的例子才有这个思路

思路：交换数组元素，使得数组中第i位存放数值(i+1)。最后遍历数组，寻找第一个不符合此要求的元素，返回其下标。整个过程需要遍历两次数组，复杂度为O(n)。

然后在复杂度这卡了一下，由于每次交换一定有一个元素在正确的位置，在下一次判断是否交换的时候由于这个元素已经在正确的位置所以不交换，因此保证最多交换n次，然后遍历数组，找出第一个不符合要求的元素，最多找n个位置。因此，复杂度为O(n)

public int firstMissingPositive(int[] A) {
        for(int i=0;i<A.length;i++){
            if(i>=0&&i<A.length&&A[i]!=i+1){
                if(A[i]-1>=A.length||A[i]-1<0||A[A[i]-1]==A[i]){
                    A[i] = -1;
                }else{
                    int temp = A[A[i]-1];
                    A[A[i]-1] = A[i];
                    A[i] = temp;
                    i--;
                }
            }
        }
        int i=0;
        for(i=0;i<A.length;i++){
            if(i+1!=A[i]){
                break;
            }
        }
        return i+1;
    }


联系
我们