算法：最大计数器 [英] Algorithm: Max Counters

问题描述

我有以下问题：

为您提供了N个计数器，最初将其设置为0，并对它们进行了两种可能的操作：

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

• increase（X）-计数器X增加1，


• max_counter-所有计数器均设置为最大值任何计数器。

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

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

• 如果A [K] = X，使得1≤X≤N，则操作K为X），


• 如果A [K] = N +1，则操作K为max_counter。

例如，给定整数N = 5且数组A使得：

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.

我做了以下解决方案，但它运行在O（NK）处，其中K =数组A的长度。

I did the following solution but it runs at O(NK) where K = length of array 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的长度？抱歉，可能会造成糟糕的编码，我正在做这些练习来改善我的编程。谢谢！

Could anyone show me how this can be better done with O(N + K) where K is the length of array A? Sorry for may terrible coding, I am doing these exercises to improve my programming. Thanks!

推荐答案

这是我想到的，但是我不确定它是否100％有效：

This is what I came up with, but I am not sure if it works 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;
}

这篇关于算法：最大计数器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！