codility之FrogRiverOne

FrogRiverOne

题目:


A small frog wants to get to the other side of a river. The frog is currently located at position 0, and wants to get to position X. Leaves fall from a tree onto the surface of the river.

You are given a non-empty zero-indexed array A consisting of N integers representing the falling leaves. A[K] represents the position where one leaf falls at time K, measured in seconds.

The goal is to find the earliest time when the frog can jump to the other side of the river. The frog can cross only when leaves appear at every position across the river from 1 to X. You may assume that the speed of the current in the river is negligibly small, i.e. the leaves do not change their positions once they fall in the river.

For example, you are given integer X = 5 and array A such that:
  A[0] = 1
  A[1] = 3
  A[2] = 1
  A[3] = 4
  A[4] = 2
  A[5] = 3
  A[6] = 5
  A[7] = 4

In second 6, a leaf falls into position 5. This is the earliest time when leaves appear in every position across the river.

Write a function:

    function solution($X, $A);

that, given a non-empty zero-indexed array A consisting of N integers and integer X, returns the earliest time when the frog can jump to the other side of the river.

If the frog is never able to jump to the other side of the river, the function should return −1.

For example, given X = 5 and array A such that:
  A[0] = 1
  A[1] = 3
  A[2] = 1
  A[3] = 4
  A[4] = 2
  A[5] = 3
  A[6] = 5
  A[7] = 4

the function should return 6, as explained above.

Assume that:

        N and X are integers within the range [1..100,000];
        each element of array A is an integer within the range [1..X].

Complexity:

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

Elements of input arrays can be modified.


大致是要求从一堆无序的数字A中, 给定一个X, 查找包含1至X的位置。
要求:
最差的时间复杂度为O(N);
最差空间复杂度O(N);

如何解决?

O(n ** 2)的解法

最简单的就是遍历A, 初始化一个数组map, 判断元素是否在map中, 不在的话则添加到map中,同时累加count, 已经存在的话则直接跳过。

由于count每次只有在新元素添加的时候才累加, 所以当count等于X的时候肯定是找到了该元素的, 这个时候跳出循环直接返回就可以了。

代码如下:


function solution($X, $A) {
    // write your code in PHP5.5
    $map = array();

    //when count equal X, mean we find all we need
    $count = 0;
    foreach ($A as $k => $v) {
        if (!in_array($v, array_keys($map))) {
            $map[$v] = 1;
            $count += 1;
        }
        if ($count == $X) {
            return  $k;
        }
    }

    return -1;
}

Ok, 可以通过, 但性能测试基本全挂了。 可能还有同学不理解为啥是O(n * n),那是因为in_array也是遍历,

在map非常大的情况的下(极端情况下), 就会高达O(n * n)。

O(n)的解法

仔细想了下, 我们其实是靠count来保证找到了所有的需要元素的, 那其实和遍历

不遍历map无关。 我们需要保证的就是count每次就在元素不存在map、添加到map

的时候被累加是ok的就行了。

我们可以简单的采用isset()来判断元素是否在map中, isset()可是O(1)的操作。

代码:


function solution($X, $A) {
    // write your code in PHP5.5
    $map = array();

    //when count equal X, mean we find all we need
    $count = 0;
    foreach ($A as $k => $v) {
        if (!isset($map[$v])) {
            $map[$v] = 1;
            $count += 1;
        } else {
            $map[$v] += 1;
        }
        if ($count == $X) {
            return  $k;
        }
    }

    return -1;
}

总结

用in_array等语言内置的函数时, 最好心理有数大概是一个什么量级的操作。

  • in_array():
    O(n)

  • isset():
    O(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