codility之MaxCounters

MissingInteger

题目:


You are given N counters, initially set to 0, and you have two possible operations on them:

        increase(X) − counter X is increased by 1,
        max counter − all counters are set to the maximum value of any counter.

A non-empty zero-indexed array A of M integers is given. This array represents consecutive operations:

        if A[K] = X, such that 1 ≤ X ≤ N, then operation K is increase(X),
        if A[K] = N + 1 then operation K is max counter.

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

the values of the counters after each consecutive operation will be:
    (0, 0, 1, 0, 0)
    (0, 0, 1, 1, 0)
    (0, 0, 1, 2, 0)
    (2, 2, 2, 2, 2)
    (3, 2, 2, 2, 2)
    (3, 2, 2, 3, 2)
    (3, 2, 2, 4, 2)

The goal is to calculate the value of every counter after all operations.

Write a function:

    function solution($N, $A);

that, given an integer N and a non-empty zero-indexed array A consisting of M integers, returns a sequence of integers representing the values of the counters.

The sequence should be returned as:

        a structure Results (in C), or
        a vector of integers (in C++), or
        a record Results (in Pascal), or
        an array of integers (in any other programming language).

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

the function should return [3, 2, 2, 4, 2], as explained above.

Assume that:

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

Complexity:

        expected worst-case time complexity is O(N+M);
        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[k] = X 小于等于N的时, 对计数器的中的第X个进行累加

  • 全部更新:

    当A[k] = x 等于N+1时, 对计数器中的所有元素均更新到最大的值

要求:

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

如何解决?

O(n*n)

先最简单的来整吧, 按照题目要求写代码


function solution($N, $A) {
    // write your code in PHP5.5
    $count_arr  = array();
    for ($i = 1; $i < = $N; $i++) {
        $count_arr[$i] = 0;
    }
    $max_count = 0;
    foreach ($A as $k => $v) {
        if ($v < = $N) {
            $count_arr[$v] += 1;
            $max_count = max($count_arr[$v], $max_count);
        } elseif ($v == $N + 1) {
            //@todo update all ret to max in count_arr
            foreach ($count_arr as $j => &$count) {
                $count = $max_count;
            }
        }
    }
    return $count_arr;
}

不过仔细想了下性能肯定不行,在全部更新count_arr的时候, 性能最坏会达到O(n*n)。

那问题就在于我们不能直接这么的去更新计数器。能不能搞成延迟写入的方式去更新呢?

延迟写入

前面的解法最大的问题在于每次都去更新count_arr的时候决定是不行的, 其实仔细想下,

大部分的更新都是没啥用的, 因为后面如果再次遇到需要全部更新的情况下, 我们还得更新一次,

相当于前面的更新操作全是白费的。 那我们为啥不能在所有的计数器算完之后, 最后统一更新一次呢?


function solution($N, $A) {
    // write your code in PHP5.5
    $count_arr  = array();
    for ($i = 1; $i < = $N; $i++) {
        $count_arr[$i] = 0;
    }
    $max_count = 0;
    //last max_count when set all count to max_count
    $peng_count = 0;
    foreach ($A as $k => $v) {
        if ($v < = $N) {
            if ($count_arr[$v] < $peng_count) {
                $count_arr[$v] = $peng_count + 1;
            } else {
                $count_arr[$v] += 1;
            }
            $max_count =  max($count_arr[$v], $max_count);
        } elseif ($v == $N + 1) {
            $peng_count = $max_count;
        }

    }

    //lazy update (update to peng_count)
    foreach ($count_arr as $k => &$count) {
        if ($count < $peng_count) {
            $count = $peng_count;
        }
    }
    return array_values($count_arr);
}

如何在延迟更新的时候正常的计算count值?

我们设置了一个peng_count的变量用来跟踪什么时候需要全部更新, 最后再一次性更新小于peng_count

的元素到peng_count。

遍历的时候先判断下是否大于peng_count, 如果小于的话那直接更新到peng_count.

如果大于peng_count, 则累加。 同时更新下计数器中的最大值max_count。

总结

  • 为啥不能用一个max_count?
    只用max_count的话会丢失需要统一更新的状态, 即使可以做到, 也非常麻烦

  • 为啥用array_values?
    官方说要返回一个array, 关联数组会躺

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