c# - 算法:最大计数器

Question

我有以下问题:

你有 N 个计数器，初始设置为 0，你可以对它们进行两种可能的操作:

• increase(X) - 计数器 X 增加 1，
• max_counter - 所有计数器都设置为任何计数器的最大值。

给出了一个由 M 个整数组成的非空零索引数组 A。这个数组代表连续的操作:

• 如果 A[K] = X，使得 1 ≤ X ≤ N，则操作 K 为 increase(X)，
• 如果 A[K] = N + 1 则操作 K 是 max_counter。

例如，给定整数 N = 5 和数组 A 使得:

A[0] = 3
A[1] = 4
A[2] = 4
A[3] = 6
A[4] = 1
A[5] = 4
A[6] = 4

每次连续操作后计数器的值将是:

(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)

目标是计算所有操作后每个计数器的值。

我做了以下解决方案，但它的运行时间为 O(NK)，其中 K = 数组 A 的长度。

public int[] solution(int N, int[] A) {
    int[] result = new int[N];
    int maximum = 0;

    for (int K = 0; K < A.Length; K++)
    {
        if (A[K] < 1 || A[K] > N + 1)
            throw new InvalidOperationException();

        if (A[K] >= 1 && A[K] <= N)
        {
            result[A[K] - 1]++;

            if (result[A[K] - 1] > maximum)
            {
                maximum = result[A[K] - 1];
            }
        }
        else
        {
            // inefficiency here
            for (int i = 0; i < result.Length; i++)
                result[i] = maximum;
        }
    }

    return result;
}

谁能告诉我如何使用 O(N + K) 更好地完成此操作，其中 K 是数组 A 的长度？抱歉，我的编码可能很糟糕，我正在做这些练习来改进我的编程。谢谢!

Answer 1

这是我想出来的，但我不确定它是否 100% 有效:

public int[] solution(int N, int[] A) {
    int[] result = new int[N];
    int maximum = 0;
    int resetLimit = 0;

    for (int K = 0; K < A.Length; K++)
    {
        if (A[K] < 1 || A[K] > N + 1)
            throw new InvalidOperationException();

        if (A[K] >= 1 && A[K] <= N)
        {
            if (result[A[K] - 1] < resetLimit) {
                result[A[K] - 1] = resetLimit + 1;
            } else {
                result[A[K] - 1]++;
            }

            if (result[A[K] - 1] > maximum)
            {
                maximum = result[A[K] - 1];
            }
        }
        else
        {
            // inefficiency here
            //for (int i = 0; i < result.Length; i++)
            //    result[i] = maximum;
            resetLimit = maximum;
        }
    }

    for (int i = 0; i < result.Length; i++)
        result[i] = Math.Max(resetLimit, result[i]);

    return result;
}