codility之PermMissingElem

PermMissingElem

题目:

A zero-indexed array A consisting of N different integers is given. The array contains integers in the range [1..(N + 1)], which means that exactly one element is missing.

Your goal is to find that missing element.

Write a function:

int solution(int A[], int N);

that, given a zero-indexed array A, returns the value of the missing element.

For example, given array A such that:


  A[0] = 2
  A[1] = 3
  A[2] = 1
  A[3] = 5
the function should return 4, as it is the missing element.

题目大致是给定非空的连续数组,求缺少的某一个元素。

要求:

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

如何解决?

O(n ** 2)的解法

最开始的想法是找到最大值,然后生成一个1至最大值的数组B。然后遍历这个数组,

检查元素在不在数组A中,如果有不在A中的则退出、返回结果。

但细想下就发现时间复杂度太高了。 不说求最大值的

时间O(n), 既然是遍历新数组、依次检查元素在不在A中, 复杂度就必然是O(n ** 2)。

为啥呢? 那是因为检查元素是否在数组A的复杂度最差肯定是O(n)的。

思路

既然时间复杂度是O(n),那就意味着我们只能顺序的扫描一遍就必须得出结果。

遍历数组一遍那是肯定少不了的, 和前面的解法对比我们能省去的就是检查元素的这个复杂度。

如果检查的操作可以降低为O(1)那就完美的解决了。 进一步想, 好像只有hash表之类的索引

才有可能是O(1)的。 想到这里, 就很简单了, 我们在遍历A的时候, 将对应的元素放入到B中,

将其标志位设置为1,标示元素已经存在。

最后我们只需要检查下B中为0的元素,即可得出A中缺少的元素。

代码如下

PHP


function solution($A) {
    // write your code in PHP5.5
    $B = range(1, count($A) + 1);
    foreach($A as $value){
        $B[$value - 1] = 0;
    }
    
    foreach($B as $value){
        if($value != 0){
            return $value;
        }
    }
}

Python


def solution(A):
    # write your code in Python 2.7

    B = range(1, len(A) + 2)

    for i in A:
        B[i - 1] = 0

    for i in B:
        if i != 0:
            return i

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