我有以下问题:
给定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的长度。很抱歉我的代码很糟糕,我正在做这些练习来提高我的编程水平。谢谢!