java codility Max-Counters

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/

你能给我一个暗示这个解决方案有什么问题吗？

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).我认为,解决这个问题的一种方法是,不是在调用操作A时显式更新整个数组,而是max_counter可以将上次更新的值保存为变量.当调用第一个操作(增量)时,您只需查看您尝试增加的值是否大于 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;
    }
}

Answer 2

问题是,当你进行大量的max_counter操作时,你会得到很多调用,Arrays.fill这使你的解决方案变得缓慢.

你应该保持一个currentMax和一个currentMin:

• 当你得到一个max_counter你刚设置currentMin = currentMax.
• 如果你得到另一个值,我们称之为i:
  • 如果位置i - 1上的值小于或等于currentMin您将其设置为currentMin + 1.
  • 否则你增加它.

在刚刚结束经过计数器阵列一次设置好一切小于currentMin到currentMin.

Answer 3

我已经开发并可能值得考虑的另一种解决方案：http : //codility.com/demo/results/demoM658NU-DYR/

Answer 4

这是这个问题的100％解决方案。

// you can also use imports, for example:
// import java.math.*;
class Solution {
    public int[] solution(int N, int[] A) {
        int counter[] = new int[N];
        int n = A.length;
        int max=-1,current_min=0;

        for(int i=0;i<n;i++){
            if(A[i]>=1 && A[i]<= N){
                if(counter[A[i] - 1] < current_min) counter[A[i] - 1] = current_min;
                counter[A[i] - 1] = counter[A[i] - 1] + 1;
                if(counter[A[i] - 1] > max) max = counter[A[i] - 1];
            }
            else if(A[i] == N+1){
                current_min = max;
            }
        }
        for(int i=0;i<N;i++){
            if(counter[i] < current_min) counter[i] =  current_min;
        }
        return counter;
    }
}