java - 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/

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

score 54 · Accepted Answer

问题来自这段代码：

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

想象一下，数组的每个元素都A用 value 初始化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;
    }
}

score 14 · Accepted Answer

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

您应该保留 acurrentMax和 a currentMin：

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

最后，只需再次遍历 counters 数组并将所有内容设置为小于currentMinto currentMin。

score 6 · Accepted Answer

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

score 6 · Accepted Answer

这是这个问题的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;
    }
}

score 2 · Accepted Answer

I'm adding another Java 100 solution with some test cases it they're helpful.

// https://codility.com/demo/results/demoD8J6M5-K3T/ 77
// https://codility.com/demo/results/demoSEJHZS-ZPR/ 100
public class MaxCounters {

  // Some testcases
  // (1,[1,2,3]) = [1]
  // (1,[1]) = [1]
  // (1,[5]) = [0]
  // (1,[1,1,1,2,3]) = 3
  // (2,[1,1,1,2,3,1]) = [4,3]
  // (5, [3, 4, 4, 5, 1, 4, 4]) = (1, 0, 1, 4, 1)
  public int[] solution(int N, int[] A) {
      int length = A.length, maxOfCounter = 0, lastUpdate = 0;
      int applyMax = N + 1;
      int result[] = new int[N];

      for (int i = 0; i < length; ++i ) {
          if(A[i] == applyMax){
              lastUpdate = maxOfCounter;
          } else if (A[i] <= N)  {
              int position = A[i]-1;
              result[position] = result[position] > lastUpdate
                                        ? result[position] + 1 : lastUpdate + 1;
              // updating the max for future use
              if(maxOfCounter <=  result[position]) {
                  maxOfCounter = result[position];
              }
          }
     }
     // updating all the values that are less than the lastUpdate to the max value
     for (int i = 0; i < N; ++i) {
         if(result[i] < lastUpdate) {
             result[i] = lastUpdate;
         }
     }
     return result;
   }
}

score 1 · Accepted Answer

vector<int> solution(int N, vector<int> &A)
{
    std::vector<int> counters(N);
    auto max = 0;
    auto current = 0;

    for (auto& counter : A)
    {
        if (counter >= 1 && counter <= N)
        {
            if (counters[counter-1] < max)
                counters[counter - 1] = max;

            counters[counter - 1] += 1;

            if (counters[counter - 1] > current)
                current = counters[counter - 1];
        }
        else if (counter > N)
            max = current;

    }

    for (auto&& counter : counters)
        if (counter < max)
            counter = max;

    return counters;
}

score 1 · Accepted Answer

我的java解决方案有详细解释100% 正确性，100% 性能：

时间复杂度O(N+M)

 public static int[] solution(int N, int[] A) {

    int[] counters = new int[N];
    //The Max value between all counters at a given time
    int max = 0;

    //The base Max that all counter should have after the "max counter" operation happens
    int baseMax = 0;

    for (int i = 0; i < A.length; i++) {

        //max counter Operation ==> updating the baseMax
        if (A[i] > N) {
            // Set The Base Max that all counters should have
            baseMax = max;

        }

        //Verify if the value is bigger than the last baseMax because at any time a "max counter" operation can happen and the counter should have the max value
        if (A[i] <= N && counters[A[i] - 1] < baseMax) {
            counters[A[i] - 1] = baseMax;
        }

        //increase(X) Operation => increase the counter value
        if (A[i] <= N) {
            counters[A[i] - 1] = counters[A[i] - 1] + 1;

            //Update the max
            max = Math.max(counters[A[i] - 1], max);
        }
    }

    //Set The remaining values to the baseMax as not all counters are guaranteed to be affected by an increase(X) operation in "counters[A[i] - 1] = baseMax;"
    for (int j = 0; j < N; j++) {
        if (counters[j] < baseMax)
            counters[j] = baseMax;
    }

    return counters;
}

score 1 · Accepted Answer

这是我的 C++ 解决方案，它在 codility 上获得了 100 分。概念与上面解释的相同。

int maxx=0;
int lastvalue=0;
void set(vector<int>& A, int N,int X)
    {
        for ( int i=0;i<N;i++)
            if(A[i]<lastvalue)
                A[i]=lastvalue;
    }

vector<int> solution(int N, vector<int> &A) {
    // write your code in C++11

    vector<int> B(N,0);
    for(unsigned int i=0;i<A.size();i++)
        {
            if(A[i]==N+1)
               lastvalue=maxx;

            else
            {   if(B[A[i]-1]<lastvalue)
                    B[A[i]-1]=lastvalue+1;
                else
                    B[A[i]-1]++;
                if(B[A[i]-1]>maxx)
                    maxx=B[A[i]-1];
            }

        }
        set(B,N,maxx);
    return B;
}

score 0 · Accepted Answer

Hera 是我的 AC Java 解决方案。这个想法与@Inwvr 解释的相同：

public int[] solution(int N, int[] A) {
        int[] count = new int[N];
        int max = 0;
        int lastUpdate = 0;
        for(int i = 0; i < A.length; i++){
            if(A[i] <= N){
                if(count[A[i]-1] < lastUpdate){
                    count[A[i]-1] = lastUpdate+1;   
                }
                else{
                    count[A[i]-1]++;
                }    
                max = Math.max(max, count[A[i]-1]);
            }
            else{
                lastUpdate = max;   
            }
        }  
        for(int i = 0; i < N; i++){
            if(count[i] < lastUpdate)
                count[i] = lastUpdate;
        }    
        return count;
    }

score 0 · Accepted Answer

  vector<int> solution(int N, vector<int> &A) 
{
    std::vector<int> counter(N, 0); 
    int max = 0;
    int floor = 0;

    for(std::vector<int>::iterator i = A.begin();i != A.end(); i++)
    {
        int index = *i-1;
        if(*i<=N && *i >= 1)
        {
            if(counter[index] < floor)
              counter[index] = floor;
            counter[index] += 1;
            max = std::max(counter[index], max);
        }
        else
        {
            floor = std::max(max, floor);
        }
    }
    for(std::vector<int>::iterator i = counter.begin();i != counter.end(); i++)
    {
       if(*i < floor)
         *i = floor;
    }
    return counter;
}

score 0 · Accepted Answer

JAVA 中的解决方案 (100/100)

    class Solution {
    public int[] solution(int N, int[] A) {
        // write your code in Java SE 8
        int[] result = new int[N];
        int base = 0;
        int max = 0;
        int needToChange=A.length;;
        for (int k = 0; k < A.length; k++) {
            int X = A[k];
            if (X >= 1 && X <= N) {

                if (result[X - 1] < base) {
                    result[X - 1] = base;
                }
                result[X - 1]++;
                if (max < result[X - 1]) {
                    max = result[X - 1];
                }
            }
            if (X == N + 1) {
                base = max;
                needToChange= X-1;

            }
        }
        for (int i = 0; i < needToChange; i++) {
            if (result[i] < base) {
                result[i] = base;
            }
        }
        return result;

    }

}

score 0 · Accepted Answer

打字稿：

function counters(numCounters: number, operations: number[]) {
const counters = Array(numCounters)

let max = 0
let currentMin = 0

for (const operation of operations) {
    if (operation === numCounters + 1) {
        currentMin = max
    } else {
        if (!counters[operation - 1] || counters[operation - 1] < currentMin) {
            counters[operation - 1] = currentMin
        }

        counters[operation - 1] = counters[operation - 1] + 1

        if (counters[operation - 1] > max) {
            max += 1
        }
    }
}

for (let i = 0; i < numCounters; i++) {
    if (!counters[i] || counters[i] < currentMin) {
        counters[i] = currentMin
    }
}

return counters

}

控制台日志（solution=${counters(5, [3, 4, 4, 6, 1, 4, 4])}）

score 0 · Accepted Answer

这是该问题的另一个 C++ 解决方案。

理由总是一样的。

避免在指令二时将所有计数器设置为最大计数器，因为这会将复杂度提高到 O(N*M)。
等到我们在单个计数器上获得另一个操作代码。
此时，算法会记住它是否满足 max_counter 并因此设置计数器值。

这里的代码：

vector<int> MaxCounters(int N, vector<int> &A) 
{
    vector<int> n(N, 0);
    int globalMax = 0;
    int localMax = 0;

    for( vector<int>::const_iterator it = A.begin(); it != A.end(); ++it)
    {
        if ( *it >= 1 && *it <= N)
        {
            // this is an increase op.
            int value = *it - 1;
            n[value] = std::max(n[value], localMax ) + 1;
            globalMax = std::max(n[value], globalMax);
        }
        else
        {
            // set max counter op.
            localMax = globalMax;
        }
    }

    for( vector<int>::iterator it = n.begin(); it != n.end(); ++it)
        *it = std::max( *it, localMax );

    return n;
}

score 0 · Accepted Answer

我只想展示 77 % - 解决方案的样子：

 public int[] solution(int N, int[] A) {
    int K = 0;
    int[] B = new int[N];
    for (int a : A)
        if (a > N) Arrays.fill(B, K);
        else K = Math.max(K, ++B[a-1]);
    return B;
}

score 0 · Accepted Answer

这是我使用 python 3.6 的解决方案。结果是 100% 的正确性，但 40% 的性能（其中大部分是因为超时）。仍然无法弄清楚如何优化此代码，但希望有人能发现它有用。

def solution(N, A):
    count = [0]*(N+1)
    for i in range(0,len(A)):
        if A[i] >=1 and A[i] <= N:
            count[A[i]] += 1
        elif A[i] == (N+1): 
            count = [max(count)] * len(count)
    count.pop(0)
    return count

score 0 · Accepted Answer

Java 100%/100%，无导入


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

    int[] counters = new int[N];

    int currentMax = 0;
    int sumOfMaxCounters = 0;
    boolean justDoneMaxCounter = false;

    for (int i = 0; i < A.length ; i++) {

        if (A[i]  <= N) {

            justDoneMaxCounter = false;
            counters[A[i]-1]++;
            currentMax = currentMax < counters[A[i]-1] ? counters[A[i]-1] : currentMax;

        }else if (!justDoneMaxCounter){

            sumOfMaxCounters += currentMax;     
            currentMax = 0;
            counters = new int[N];
            justDoneMaxCounter = true;

        }
    }


    for (int j = 0; j < counters.length; j++) {
        counters[j] = counters[j] + sumOfMaxCounters;
    }

    return counters;
}

score 0 · Accepted Answer

遵循我在 JAVA (100/100) 中的解决方案。

public boolean isToSum(int value, int N) {
    return value >= 1 && value <= N;
}

public int[] solution(int N, int[] A) {
    int[] res = new int[N];
    int max =0;
    int minValue = 0;

    for (int i=0; i < A.length; i++){
        int value = A[i];
        int pos = value -1;
        if ( isToSum(value, N)) {
            if( res[pos] < minValue) {
                res[pos] = minValue;
            }
            res[pos] += 1;
            if (max < res[pos]) {
                max = res[pos];
            }
        } else {
            minValue = max;
        }
    }

    for (int i=0; i < res.length; i++){
        if ( res[i] < minValue ){
            res[i] = minValue;
        }
    }
    return res;
}

score 0 · Accepted Answer

我的解决方案是：

public class Solution {  

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

            int[] counters = new int[N];
            int[] countersLastMaxIndexes = new int[N];
            int maxValue = 0;
            int fixedMaxValue = 0;
            int maxIndex = 0;
            for (int i = 0; i < A.length; i++) {
                if (A[i] <= N) {
                    if (countersLastMaxIndexes[A[i] - 1] != maxIndex) {
                        counters[A[i] - 1] = fixedMaxValue;
                        countersLastMaxIndexes[A[i] - 1] = maxIndex;

                    }
                    counters[A[i] - 1]++;
                    if (counters[A[i] - 1] > maxValue) {
                        maxValue = counters[A[i] - 1];
                    }
                } else {
                    maxIndex = i;
                    fixedMaxValue = maxValue;
                }

            }
            for (int i = 0; i < countersLastMaxIndexes.length; i++) {
                if (countersLastMaxIndexes[i] != maxIndex) {
                    counters[i] = fixedMaxValue;
                    countersLastMaxIndexes[i] = maxIndex;
                }
            }

            return counters;
        }
}

score 0 · Accepted Answer

在此处输入链接描述

用 O ( N + M ) 得到 100% 的结果

class Solution {
public int[] solution(int N, int[] A) {
    // write your code in Java SE 8

    int max = 0;
    int[] counter = new int[N];
    int upgrade = 0;

    for ( int i = 0; i < A.length; i++ )
    {
        if ( A[i] <= N )
        {
            if ( upgrade > 0 && upgrade > counter[A[i] - 1 ] )
            {
                counter[A[i] - 1] = upgrade; 
            }

            counter[A[i] - 1 ]++;

            if ( counter[A[i] - 1 ] > max )
                {
                    max = counter[A[i] - 1 ];
                }
        }
        else
        {
            upgrade = max;
        }

    }

    for ( int i = 0; i < N; i++ )
    {
        if ( counter[i] < upgrade)
        {
            counter[i] = upgrade;
        }
    }

    return counter;

}

}

score 0 · Accepted Answer

这是 python 中的解决方案，具有 100% Codility Max counter 100%

def solution(N, A):
"""
Solution at 100% - https://app.codility.com/demo/results/trainingUQ95SB-4GA/
Idea is first take the counter array of given size N
take item from main A one by one + 1 and put in counter array , use item as index
keep track of last max operation
at the end replace counter items with max of local or counter item it self
:param N:
:param A:
:return:
"""
global_max = 0
local_max = 0
# counter array
counter = [0] * N

for i, item in enumerate(A):
    # take item from original array one by one - 1 - minus due to using item as index
    item_as_counter_index = item - 1
    # print(item_as_counter_index)
    # print(counter)
    # print(local_max)
    # current element less or equal value in array and greater than 1
    #         if A[K] = X, such that 1 ≤ X ≤ N, then operation K is increase(X),
    if N >= item >= 1:
        # max of local_max counter at item_as_counter_index
        # increase counter array value and put in counter array
        counter[item_as_counter_index] = max(local_max, counter[item_as_counter_index]) + 1
        # track the status of global_max counter so far
        # this is operation K
        global_max = max(global_max, counter[item_as_counter_index])
    #         if A[K] = N + 1 then operation K is max counter.
    elif item == N + 1:
        # now operation k is as local max
        # here we need to replace all items in array with this global max
        # we can do using for loop for array length but that will cost bigo n2 complexity
        # example -  for i, item in A: counter[i] = global_max
        local_max = global_max
    # print("global_max each step")
    # print(global_max)

# print("local max so far....")
# print(local_max)
# print("counter - ")
# print(counter)
# now counter array - replace all elements which are less than the local max found so far
# all counters are set to the maximum value of any counter
for i, item in enumerate(counter):
    counter[i] = max(item, local_max)

return counter

结果 = 解决方案(1, [3, 4, 4, 6, 1, 4, 4]) print("Sol" + str(result))

score 0 · Accepted Answer

在我的 Java 解决方案中，我仅在需要时更新了解决方案 [] 中的值。最后用正确的值更新了解决方案[]。

public int[] solution(int N, int[] A) {
    int[] solution = new int[N];
    int maxCounter = 0;
    int maxCountersSum = 0;
    for(int a: A) {
        if(a >= 1 && a <= N) {
            if(solution[a - 1] < maxCountersSum)
                solution[a - 1] = maxCountersSum;
            solution[a - 1]++;
            if(solution[a - 1] > maxCounter)
                maxCounter = solution[a - 1];
        }
        if(a == N + 1) {
            maxCountersSum = maxCounter;
        }
    }
    for(int i = 0; i < N; i++) {
        if(solution[i] < maxCountersSum)
            solution[i] = maxCountersSum;
    }

    return solution;
}

score 0 · Accepted Answer

100%, O(m+n)

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

    int[] counters = new int[N];
    int maxAIs = 0;
    int minAShouldBe = 0;

    for(int x : A) {
        if(x >= 1 && x <= N) {
            if(counters[x-1] < minAShouldBe) {
                counters[x-1] = minAShouldBe;
            }

            counters[x-1]++;

            if(counters[x-1] > maxAIs) {
                maxAIs = counters[x-1];
            }
        } else if(x == N+1) {
            minAShouldBe = maxAIs;
        }
    }

    for(int i = 0; i < N; i++) {
        if(counters[i] < minAShouldBe) {
            counters[i] = minAShouldBe;
        }
    }

    return counters;
}

score 0 · Accepted Answer

这是我的python解决方案：

def solution(N, A):
    # write your code in Python 3.6
    RESP = [0] * N
    MAX_OPERATION = N + 1
    current_max = 0
    current_min = 0
    for operation in A:
        if operation != MAX_OPERATION:
            if RESP[operation-1] <= current_min:
                RESP[operation-1] = current_min + 1
            else:
                RESP[operation-1] += 1

            if RESP[operation-1] > current_max:
                current_max = RESP[operation-1]
        else:
            if current_min == current_max:
                current_min += 1
            else:
                current_min = current_max

    for i, val in enumerate(RESP):
        if val < current_min:
            RESP[i] = current_min
    return RESP

score 0 · Accepted Answer

这是我的代码，但它的 88% 原因是 10000 个元素需要 3.80 秒而不是 2.20

类解决方案{

boolean maxCalled;

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

int max =0;
int [] counters = new int [N];
    int temp=0;
    int currentVal = 0;
    for(int i=0;i<A.length;i++){
    currentVal = A[i];
    if(currentVal <=N){
        temp = increas(counters,currentVal);
        if(temp > max){
        max = temp;
        }
    }else{
        if(!maxCalled)
        maxCounter(counters,max);
    }

    }

    return counters;

}


int increas (int [] A, int x){  
 maxCalled = false;
 return ++A[x-1];  
 //return t;
}

void maxCounter (int [] A, int x){
 maxCalled = true;
  for (int i = 0; i < A.length; i++) {
 A[i] = x;
  }

}

}

score 0 · Accepted Answer

使用 applyMax 记录最大操作

时间复杂度：O(N + M)

class Solution {
    public int[] solution(int N, int[] A) {
        // write your code in Java SE 8
        
        int max = 0, applyMax = 0;;
        int[] result = new int[N];
        
        for (int i = 0; i < A.length; ++i) {
            int a = A[i];
            
            if (a == N + 1) {
                applyMax = max;
            }
            
            if (1 <= a && a <= N) {
                result[A[i] - 1] = Math.max(applyMax, result[A[i] - 1]);
                max = Math.max(max, ++result[A[i] - 1]);
            }
        }
        
        for (int i = 0; i < N; ++i) {
            if (result[i] < applyMax) {
                result[i] = applyMax;
            }
        }
        
        return result;
    }
}

score 0 · Accepted Answer

Arrays.fill()在数组交互中调用使程序 O(N^2)

这是一个可能的解决方案，它具有 O(M+N) 运行时间。

这个想法是 -

对于第二个操作，跟踪通过增量获得的最大值，这是我们直到当前迭代的基础值，任何值都不能小于这个。

对于第一个操作，如果需要，在增量之前将值重置为基值。

public static int[] solution(int N, int[] A) { int counters[] = new int[N];

int base = 0;
int cMax = 0;

for (int a : A) {
    if (a > counters.length) {
        base = cMax;
    } else {
        if (counters[a - 1] < base) {
            counters[a - 1] = base;
        }

        counters[a - 1]++;

        cMax = Math.max(cMax, counters[a - 1]);
    }
}

for (int i = 0; i < counters.length; i++) {
    if (counters[i] < base) {
        counters[i] = base;
    }
}

return counters;

}

score 0 · Accepted Answer

Here is a c++ solution with 100% score:

#include <algorithm>
#include <assert.h>

void increase(int N, std::vector<int>& counters, int minCounter, int& max){
    //assert(N >= 1 && size_t(N - 1) < counters.size());
    auto n = counters[N - 1];
    counters[N - 1] = n <= minCounter ? minCounter + 1 : n + 1;
    if(counters[N - 1] > max) {
        max = counters[N - 1];
    }
}

vector<int> solution(int N, vector<int> &A) {
    auto minCounter = 0;
    auto max = 0;
    std::vector<int> counters(N, 0);
    auto allEquals = true;
    for(auto i : A) {
        if(1 <= i && i <= N) {
            increase(i, counters, minCounter, max);
            allEquals = false;
        } else if(i == N + 1 && !allEquals) {
            minCounter = max;
            allEquals = true;
        }
    }
    
    for(auto& c : counters) {
        c = std::max(c, minCounter);
    }
    return counters;
}

score 0 · Accepted Answer

100 分 JavaScript 解决方案，包括性能改进以忽略重复的 max_counter 迭代：

function solution(N, A) {
    let max = 0;
    let counters = Array(N).fill(max);
    let maxCounter = 0;

    for (let op of A) {
        if (op <= N && op >= 1) {
            maxCounter = 0;
            if (++counters[op - 1] > max) {
                max = counters[op - 1];
            }
        } else if(op === N + 1 && maxCounter === 0) {
            maxCounter = 1;
            for (let i = 0; i < counters.length; i++) {
                counters[i] = max;   
            }
        }
    }

    return counters;
}

score 0 · Accepted Answer

蟒蛇解决方案：100％100％

def solution(N, A):
    c = [0] * N

    max_element = 0
    base = 0
    for item in A:

        if item >= 1 and N >= item:
            c[item-1] = max(c[item-1], base) + 1
            max_element = max(c[item - 1], max_element)
        elif item == N + 1:
            base = max_element

    for i in range(N):
        c[i] = max (c[i], base)
    return c
    pass

score 0 · Accepted Answer

我的 Java 解决方案。它提供 100% 但很长（相比之下）。我使用 HashMap 来存储计数器。

检测到的时间复杂度：O(N + M)

import java.util.*;

class Solution {
  final private Map<Integer, Integer> counters = new HashMap<>();
  private int maxCounterValue = 0;
  private int maxCounterValueRealized = 0;

  public int[] solution(int N, int[] A) {
    if (N < 1) return new int[0];

    for (int a : A) {
      if (a <= N) {
        Integer current = counters.putIfAbsent(a, maxCounterValueRealized + 1);
        if (current == null) {
          updateMaxCounterValue(maxCounterValueRealized + 1);
        } else {
          ++current;
          counters.replace(a, current);
          updateMaxCounterValue(current);
        }
      } else {
        maxCounterValueRealized = maxCounterValue;
        counters.clear();
      }
    }

    return getCountersArray(N);
  }

  private void updateMaxCounterValue(int currentCounterValue) {
    if (currentCounterValue > maxCounterValue)
      maxCounterValue = currentCounterValue;
  }

  private int[] getCountersArray(int N) {
    int[] countersArray = new int[N];

    for (int j = 0; j < N; j++) {
      Integer current = counters.get(j + 1);
      if (current == null) {
        countersArray[j] = maxCounterValueRealized;
      } else {
        countersArray[j] = current;
      }
    }

    return countersArray;
  }
}

score 0 · Accepted Answer

def sample_method(A,N=5):
    initial_array = [0,0,0,0,0]
for i in A:

    if(i>=1):
      if(i<=N):
        initial_array[i-1]+=1
      else:
        for a in range(len(initial_array)):
          initial_array[a]+=1
    print i
    print initial_array

score 0 · Accepted Answer

在上面的一些帮助下，我刚刚在 PHP 中获得了 100

function solution($N, $A) {
    $B = array(0);
    $max = 0;

    foreach($A as $key => $a) {
        $a -= 1;
        if($a == $N) {
            $max = max($B);
        } else {
            if(!isset($B[$a])) {
                $B[$a] = 0;
            }

            if($B[$a] < $max) {
                $B[$a] = $max + 1;
            } else {
                $B[$a] ++;
            }

        }

    }

    for($i=0; $i<$N; $i++) {
        if(!isset($B[$i]) || $B[$i] < $max) {
            $B[$i] = $max;
        }

    }

    return $B;


}

score 0 · Accepted Answer

这条线增加了复杂性：

Arrays.fill(countersArray, currentMax);

解决方案是仅在处理时将计数器设置为最大值，最后添加一个最终循环以将所有内容与最后一个最大值对齐。

这是另一个分数为 %100 的 Java 解决方案：

https://app.codility.com/demo/results/trainingA83U7Y-ESQ/

public int[] solution(int N, int[] A) {
    int[] counters = new int[N];
    int max = 0;
    int lastMaximization = 0;
    for (int command : A) {
        if (command < N + 1) {
            int index = command - 1;
            counters[index] = Math.max(lastMaximization, counters[index]) + 1;
            max = Math.max(max, counters[index]);
        } else {
            lastMaximization = max;
        }
    }

    for (int i = 0; i < counters.length; i++) {
        counters[i] = Math.max(lastMaximization, counters[i]);
    }

    return counters;
}

score 0 · Accepted Answer

使用 Java 的 Codility 100% 得分

import java.util.Arrays;
class Solution {
    public int[] solution(int N, int[] A) {
        // write your code in Java SE 8

        int[] res = new int[N];

        int counterMax = 0;
        int lastMax = 0;


        for(int i=0;i<A.length;i++){
            if( (A[i]>=1) && (A[i] <= N) ){
                
                if(res[A[i]-1] <= lastMax){
                    res[A[i]-1] = lastMax + 1;
                }
                else if(res[A[i]-1] > lastMax ){
                    res[A[i]-1] += 1;
                }


                if( res[A[i]-1] > counterMax ){
                    counterMax = res[A[i]-1];
                }
                //System.out.println(Arrays.toString(res));
             
            }
            else{
                
                lastMax = counterMax;
                //Arrays.fill(res,counterMax);
                //System.out.println(Arrays.toString(res));
            }
        }


        for(int i=0; i< res.length; i++){
            if(res[i] <= lastMax){
                res[i] = lastMax;
            }
        }
        return res;

    }

java - java codility Max-Counters

34 回答 34

Related

Reference