java codility 最大计数器

Question

我一直在努力解决以下任务：

给定 N 个计数器，初始设置为 0，并且对它们有两种可能的操作：

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

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

     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.

例如，给定整数 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)

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

 struct Results {
  int * C;
  int L;
};

写一个函数：

 struct Results solution(int N, int A[], int M);

给定一个整数 N 和一个由 M 个整数组成的非空零索引数组 A，返回表示计数器值的整数序列。

该序列应返回为：

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

例如，给定：

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

如上所述，该函数应返回 [3, 2, 2, 4, 2]。

假使，假设：

     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].

复杂：

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

可以修改输入数组的元素。

这是我的解决方案：

 import java.util.Arrays;

class Solution {
    public int[] solution(int N, int[] A) {

        final int condition = N + 1;
        int currentMax = 0;
        int countersArray[] = new int[N];

        for (int iii = 0; iii < A.length; iii++) {
            int currentValue = A[iii];
            if (currentValue == condition) {
                Arrays.fill(countersArray, currentMax);
            } else {
                int position = currentValue - 1;
                int localValue = countersArray[position] + 1;
                countersArray[position] = localValue;

                if (localValue > currentMax) {
                    currentMax = localValue;
                }
            }

        }

        return countersArray;
    }
}

这是代码估值： https ://codility.com/demo/results/demo6AKE5C-EJQ/

你能告诉我这个解决方案有什么问题吗？

原文由 pshemek 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

问题来自这段代码：

 for (int iii = 0; iii < A.length; iii++) {
     ...
     if (currentValue == condition) {
         Arrays.fill(countersArray, currentMax);
     }
     ...
}

假设数组的每个元素 A 都被初始化为值 N+1 。由于函数调用 Arrays.fill(countersArray, currentMax) 的时间复杂度为 O(N) 那么总体而言，您的算法的时间复杂度为 O(M * N) 。我认为，一种解决此问题的方法不是在调用 max_counter 操作时显式更新整个数组 A --- 操作，而是将上次更新的值保留为变量。当调用第一个操作（递增）时，您只需查看您尝试递增的值是否大于 last_update 。如果是，您只需将值更新为 1 ，否则将其初始化为 last_update + 1 。当调用第二个操作时，您只需将 --- last_update 更新为 current_max 。最后，当您完成并尝试返回最终值时，您再次将每个值与 last_update 进行比较。如果它更大，您只需保留该值，否则您返回 last_update

 class Solution {
    public int[] solution(int N, int[] A) {

        final int condition = N + 1;
        int currentMax = 0;
        int lastUpdate = 0;
        int countersArray[] = new int[N];

        for (int iii = 0; iii < A.length; iii++) {
            int currentValue = A[iii];
            if (currentValue == condition) {
                lastUpdate = currentMax
            } else {
                int position = currentValue - 1;
                if (countersArray[position] < lastUpdate)
                    countersArray[position] = lastUpdate + 1;
                else
                    countersArray[position]++;

                if (countersArray[position] > currentMax) {
                    currentMax = countersArray[position];
                }
            }

        }

        for (int iii = 0; iii < N; iii++) {
           if (countersArray[iii] < lastUpdate)
               countersArray[iii] = lastUpdate;
        }

        return countersArray;
    }
}

原文由 sve 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

问题是，当您获得大量 max_counter 操作时，您会收到大量对 Arrays.fill 的调用，这会使您的解决方案变慢。

你应该保留一个 currentMax 和一个 currentMin ：

• 当您得到 max_counter 时，您只需设置 currentMin = currentMax 。
• 如果你得到另一个值，我们称之为 i ：
  • 如果位置 i - 1 的值小于或等于 currentMin 您将其设置为 currentMin + 1 。
  • 否则你增加它。

最后再次遍历计数器数组并将小于 currentMin 的所有内容设置为 currentMin 。

原文由 andredor 发布，翻译遵循 CC BY-SA 3.0 许可协议