这个题目是Max Counters的Codility挑战，有一个解决方案存在问题。

Question

我最近在做Codility的测试，卡在了“Max Counters”这一题上（链接：https://codility.com/demo/take-sample-test/max_counters）。我的第一个明显的解决方案如下：

def solution(N, A):

    counters = N * [0];    

    for a in A:
        if 1 <= a <= N:
            counters[a - 1] += 1;
        elif a == N + 1:
            counters = N * [max(counters)];

    return counters

目前的方法可以正常运行，但由于每次调用max counters都会填充整个数组，所以耗费时间较长。

因此，我提出了以下解决方案，对于小规模的输入数据表现良好，但对于中等和大型数据则随机出现错误结果。

def solution(N, A):

    counters = N * [0];
    current_max = 0;
    last_update = 0;

    for a in A:
        if 1 <= a <= N:
            counters[a - 1] += 1;

            if counters[a - 1] < last_update:
                counters[a - 1] = last_update + 1;

            if counters[a - 1] > current_max:
                current_max = counters[a - 1];

        elif a == N + 1:
            last_update = current_max;

    for i in xrange(len(counters)):
        if counters[i] < last_update:
            counters[i] = last_update;           

    return counters

我似乎无法弄清楚它有什么问题。

编辑：结果 - http://codility.com/demo/results/demoQA7BVQ-NQT/

- jaho

---

对于你的问题来说是无界的，但在Python中你不需要分号。 - chaiyachaiya

没错。有一段时间没有使用 Python 了。 - jaho

最后一个循环的目的是什么？ - chaiyachaiya

我不明白。将相同的值放入所有计数器的唯一方法是使A[K]=N+1。 为什么要将计数器的每个元素与上次更新进行比较？ - chaiyachaiya

这是为了避免在每次循环中更新整个数组，而是仅在循环后一次性更新那些输入数组中不存在的计数器。如果您在每次循环中打印A、current_max和last_update，您将看到正在发生的情况。 - jaho

输入 (3，[3,3,4,3]) 将得到 (0,0,1) -> (0,0,2) -> (0,0,2) -> (0,0,3)。最后一次循环将使它变为 (2,2,3)，这是正确的答案。 - jaho

Answer 1

这个（Python，得分100分）要注意的秘密并不是每次收到将所有计数器增加到新最小值的指令时更新所有计数器。这会在每个情况中涉及到每个计数器的操作，这是60％和100％分数之间的区别。

相反，通过跟踪当前的最小值和最大值来避免此问题；对于您访问的每个计数器使用和更新它们。

然后，在处理完所有指令后，因为可能存在未被触及其自己的个人更新自上次全部更新指令以来的计数器，请经过计数器本身并确保它们处于最小值。

def solution(N, A):
    res = [0] * N
    max_val = 0
    last_update = 0
    n1 = N+1
    for i in A:
        if i < n1:
            if res[i-1] < last_update:
                res[i-1] = last_update

            res[i-1]+=1

            if res[i-1] > max_val:
                max_val = res[i-1]
        else:
            last_update = max_val

    for i in xrange(len(res)):
        if res[i] < last_update:
            res[i] = last_update

    return res

http://codility.com/demo/results/demoF3AMPT-FVN/

- jacoor

Answer 2

这是@jacoor解决方案的修改版本，采用更具特色的python编程语言和变量名，并且if语句的条件更贴近问题描述。

def fast_solution(N, A):
    counters = [0] * N
    max_counter = 0
    last_update = 0

    for K,X in enumerate(A): # O(M)
        if 1 <= X <= N:
            counters[X-1] = max(counters[X-1], last_update)
            counters[X-1] += 1
            max_counter = max(counters[X-1], max_counter)
        elif A[K] == (N + 1):
            last_update = max_counter

    for i in xrange(N): # O(N)
        counters[i] = max(counters[i], last_update)

    return counters

https://codility.com/demo/results/demo6KPS7K-87N/

- Al Johri

Answer 3

一个问题在这里：

counters[a - 1] += 1
if counters[a - 1] < last_update:
    counters[a - 1] = last_update + 1

如果 counters[a - 1] 是 last_update - 1，会怎样？

- jonrsharpe

---

当然。将第一行移动到else语句之后可以解决这个问题。 - jaho

Answer 4

JavaScript 100/100

function solution(N, A) {
    var max = 0,
        offset = 0,
        counters = Array.apply(null, Array(N)).map(function () {return 0;});
        
    A.forEach(function (d) {
        if (d === N + 1) {
            offset = max;
        }
        else {
            counters[d-1] = Math.max(offset + 1, counters[d-1] + 1);
            max = Math.max(counters[d-1], max);
        }
    });
    
    counters.map(function (d, i) {
        if (d < offset) {
            counters[i] = offset;
        }
    });
    
    return counters;
}

- piUek

Answer 5

C# - 一个100/100的解决方案

public int[] solution(int N, int[] A) {
    // write your code in C# 6.0 with .NET 4.5 (Mono)
    int[] counter = new int[N];
    int maxValue = 0;
    int minValue = 0;
    for(int i=0;i<A.Length;i++)
    {
        //less than or equal to length N
        if(A[i] <= N)
        {
            if(counter[A[i] - 1] < minValue)
            {
                counter[A[i] - 1] = minValue;
            }
            counter[A[i] - 1] += 1;
            if(counter[A[i] - 1] > maxValue)
            {
                maxValue = counter[A[i] - 1];
            }
        }
        else if(A[i] == N+1)
        {
            minValue = maxValue;
        }
    }
    for(int j=0;j<counter.Length;j++)
    {
        if(counter[j] < minValue)
        {
            counter[j] = minValue;
        }
    }
    return counter;
}

- albtvenki

Answer 6

你可以看一下我的解决方案（尽管是用C#编写的）：

public static int[] solution(int N, int[] A)
    {
        // write your code in C# with .NET 2.0
        var counters = new int[N];
        var defaultValueToInitialize = 0;
        var maxElement = 0;


        //initializing the counters values, without increasing the N+1 actions
        foreach (var num in A)
        {
            if (num == N + 1)
            {
                defaultValueToInitialize = maxElement;
                counters = new int[N];
            }
            else
            {
                counters[num - 1]++;
                if (counters[num - 1] + defaultValueToInitialize > maxElement)
                    maxElement = counters[num - 1] + defaultValueToInitialize;
            }

        }

        //adding the increased default value to each cell

        for (int i = 0; i < counters.Length; i++)
        {
            counters[i] += defaultValueToInitialize;
        }

        return counters;
    }

- IdoT

---

谢谢您的发帖，但是在foreach循环中，“counters = new int[N];”不是必要的吗？（编辑：哦，我明白了。那是必要的。它将计数器重置为全零。） - sgryzko

Answer 7

考虑这个用 Ruby 实现的 100/100 解决方案：

# Algorithm:
#
# * Maintain a maximum value.
# * For each `increase(X)` command update respective counter.
# * For each `max_counter` command save the current max as `set_max` for later use.
# * Once the loop is over, make an adjustment pass to set all values less than `set_max` to `set_max`.
def solution(n, commands)
  max = set_max = 0
  counters = Array.new(n, 0)

  commands.each do |cmd|
    if cmd <= n
      # This is an `increase(X)` command.
      value = [counters[cmd - 1], set_max].max + 1
      counters[cmd - 1] = value
      max = [value, max].max
    else
      # This is a `max_counter` command.
      # Just update `set_max`.
      set_max = max
    end
  end

  # Finalize -- set counters less than `set_max` to `set_max`.
  counters.map! {|value| [value, set_max].max}

  # Result.
  counters
end

#--------------------------------------- Tests

def test
  sets = []
  sets << ["1", [1], 1, [1]]
  sets << ["sample", [3, 2, 2, 4, 2], 5, [3, 4, 4, 6, 1, 4, 4]]

  sets.each do |name, expected, n, commands|
    out = solution(n, commands)
    raise "FAILURE at test #{name.inspect}: #{out.inspect} != #{expected.inspect}" if out != expected
  end

  puts "SUCCESS: All tests passed"
end

- Alex Fortuna

Answer 8

Python

from collections import Counter


def solution(N, A):
    stop = [i for i in range(len(A)) if A[i] > N]
    old = val = 0
    for s in stop:
        o = A[old:s]
        if o:
            val += max(Counter(o).values())
        old = s + 1
    c = [val] * N
    start = 0 if not stop else stop[-1] + 1
    for i in A[start:]:
        c[i-1] += 1
    return c

- Aleksey

Answer 9

Python 100%

以下解决方案比先前的 Python 解决方案更简单易懂，您可以使用 set() 每次找到一个新的可能最大数时添加它。之后，当 A[i] 等于 N + 1 时，您可以使用集合中找到的最大数字更新计数器，并再次重置它，因为旧的最大值将小于即将出现的最大值并且不需要。因此，我们清除集合的那一行非常重要，以通过所有性能测试。

检测到的时间复杂度为：O(N + M)

def solution(N, A):
    
    counters = [0] * N
    max_numbers = set()
    
    for i in range(0, len(A)):

        if 1 <= A[i] <= N:

            index = A[i]-1
            counters[index] += 1
            max_numbers.add(counters[A[i]-1])

        elif A[i] == N + 1 and len(max_numbers) > 0:

            counters = [max(max_numbers)] * N
            max_numbers.clear()

    return counters

- Mohamad Ghaith Alzin

Answer 10

使用Python的100%解决方案——在每次迭代中跟踪最大值而不是每次出现N+1时计算它有助于解决问题。

def solution(N, A):
    counters = [0] * N
    all_max = list(set(A))
    if len(all_max) == 1 and all_max[0] == N + 1:
        return counters

    the_max = 0
    for i in A:
        if i == N + 1:
            counters = [the_max] * N
        elif i > N + 1:
            continue
        else:
            counters[i-1] += 1
            if counters[i-1] > the_max:
                the_max = counters[i-1]
    return counters

- gerardstreet

---

你的回答可以通过添加更多支持信息来改进。请点击[编辑]以添加更多细节，如引用或文档，以便他人确认你的答案正确无误。你可以在帮助中心找到更多关于如何编写好答案的信息。 - Community