codility之MissingInteger

MissingInteger

题目:


Write a function:

    function solution($A);

that, given a non-empty zero-indexed array A of N integers, returns the minimal positive integer (greater than 0) that does not occur in A.

For example, given:
  A[0] = 1
  A[1] = 3
  A[2] = 6
  A[3] = 4
  A[4] = 1
  A[5] = 2

the function should return 5.

Assume that:

        N is an integer within the range [1..100,000];
        each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].

Complexity:

        expected worst-case time complexity is O(N);
        expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.


题目大致是给定数组A,求不在A中的最小的正整数。

要求:

时间复杂度O(n)、空间复杂度为O(n)。

如何解决?

思路

老规则了, O(n)肯定是只能遍历一遍。

直接双重循环遍历肯定是不行的。 我们可以借鉴前面的方法, 初始化一个数组map, 把1-N的

所有数组都存进去(如$map[4] = 1), 然后遍历A的时候出现在A里面的那就去更新map($map[4] = 0), 最后我们检查map数组就可以拿到

不在A中的最小整数了,map为第一个值为1的元素对应的key就是我们的结果。

代码如下


function solution($A) {
    // write your code in PHP5.5
    $map = array();
    for ($i = 1; $i < = count($A); $i++) {
        $map[$i] = 1;
    }

    foreach ($A as $k => $v) {
        $map[$v] = 0;
    }

    foreach ($map as $k => $v) {
        if ($v == 1) {
            return  $k;
        }
    }
    return max($A) + 1;
}

边界处理

还有一种可能那就是1-N所有的元素都出现过了, 那对应的我们要求的最小值其实应该是A中的最大值+1

Leave a Reply

Your email address will not be published. Required fields are marked *


To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax