leetcode: 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.

原问题链接：https://leetcode.com/problems/first-missing-positive/

 

问题分析

　　这个问题粗看起来几乎没有什么好的办法可以解决。因为这里是对应着一个数组，它里面的元素的值可以为正也可以为负，同时有的值还可能出现多次。而且这个问题里比较苛刻的地方就是要求运行时间为O(n) 而且只能使用常量的空间。所以也不能额外申请别的数据结构来存储数据。

　　似乎没什么办法可以解决。不过问题里有一个细节可以起到一定的效果。就是要判断它的首个缺失的正整数时，它是从数字１开始往后的。那就是说如果这个数组里如果没有１，那么假设最终将它里面的负数部分挪走而且排序之后，那么它将不会是以１开头。也就是说它缺失的就是数字１。所以说，如果我们能够达到这么一个效果，就是将所有的正数都按照排序的结果调整到数组里，而且和它们所在的索引位置一致就好了。比如说下标为１的数组元素a[1] = 3。那么它将会被放到数组里第３个位置的地方，也就是索引为２的地方。

　　要能够对元素这么调整得到一个排序的效果同时其时间复杂度为O(n)的方法。从这个角度来看选择不多。一个典型的方法就是counting sort。在这里能不能用上这种方法的思路呢？

　　在实际counting sort的方法里，因为要对元素的个数进行计数，额外使用了一个数组。而且那里是假设所有的元素取值都在数组长度的范围内。所以这里不能直接照搬过来。但是我们也有了这么一个思路。就是如果我们碰到数组里某个元素的时候，假设为a[i]。我们可以根据a[i]的值来处理。假设a[i] >= 1 && a[i] <= n (n为数组长度)。这个时候，表示这个值可以映射到数组里。我们可以将它放到它在理想排序后情况下的位置。也就是a[a[i] - 1]这个地方。因为我们这里取的所有值都是从１到n，而实际数组的索引是从０开始，所以这里要减一。嗯，这样的一个调整可以实现将一个元素调整到它理想的位置。但是这里要将所有符合条件的元素都调整到它理想的地方，光直接这么交换能行吗？

　　比如说有数组[3, 4, 2, -1]。如果我们每次碰到一个在合法范围内的值就光做一个交换的话，它每次变化的情况如下：

　　[2, 4, 3, -1], [2, -1, 3, 4]。最终因为一些位置的交换我们将漏过一些元素。所以，当我们将a[i]和a[a[i] - 1]的位置调整后还应该看现在a[i]这个位置的值的情况。所以我们应该用一个循环来调整这些值。这里的循环有几个条件，一个是要保证当前a[i]的值在[1, n]区间内。所以有a[i] >= 1 && a[i] <= n。另外，这个循环要终止必然要使得a[i] == i + 1的情况。在这种情况下它其实已经在它所需要放的位置了。还有一种情况就是当a[i] == a[a[i] - 1]。就是它和它所要交换的元素值是相同的。这是对应有出现重复的元素的情况。这样我们就得到一个合理的调整步骤了。

　　剩下的事情就是来判断这个缺失的正整数了。我们需要遍历一次这个数组，并且判断a[i] == i + 1这个情况。如果相同，则继续下一个，否则i + 1就是缺失的值。还有一种情况是如果循环结束了还没有碰到上述条件的，那就说明这个数字数组长度加１。

 　　最终实现的代码如下：

 

public class Solution {

    public int firstMissingPositive(int[] a) {
        if (a == null || a.length == 0) {
            return 1;
        }    
        int n = a.length;
        for (int i = 0; i < n; i++) {
            while (a[i] >= 1 && a[i] <= n && a[i] != i + 1 && a[i] != a[a[i] - 1]) {
                int j = a[i] - 1;
                swap(a, i, j);
            }
        }
        for (int i = 0; i < n; i++) {
            if (a[i] != i + 1) {
                return i + 1;
            }
        }
        return n + 1;
    }
    
    public void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

 

总结

　　这个问题难在对各种细节的处理。很容易因为一种情况而忽略了其他的条件。能够用简短的代码来描述这些步骤还是值得仔细推敲的。

评论

1 楼 shihengli2010 2017-07-04  

解释得通俗易懂