java codility 最大计数器

java codility Max-Counters

提问by pshemek

I have been trying to solve the below task:

我一直在尝试解决以下任务：

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

您有 N 个计数器，最初设置为 0，您可以对它们进行两种可能的操作：

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

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

给出了一个由 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.

For example, given integer N = 5 and array A such that:

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

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.

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

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

Write a function:

写一个函数：

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

that, given an integer N and a non-empty zero-indexed array A consisting of M integers, returns a sequence of integers representing the values of the counters.

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

The sequence should be returned as:

该序列应返回为：

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

For example, given:

例如，给定：

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

the function should return [3, 2, 2, 4, 2], as explained above.

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

Assume that:

假使，假设：

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

Complexity:

复杂：

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

Elements of input arrays can be modified.

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

Here is my solution:

这是我的解决方案：

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;
    }
}

Here is the code valuation: https://codility.com/demo/results/demo6AKE5C-EJQ/

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

Can you give me a hint what is wrong with this solution?

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

采纳答案by sve

The problem comes with this piece of code:

问题来自这段代码：

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

Imagine that every element of the array Awas initialized with the value N+1. Since the function call Arrays.fill(countersArray, currentMax)has a time complexity of O(N)then overall your algorithm will have a time complexity O(M * N). A way to fix this, I think, instead of explicitly updating the whole array Awhen the max_counteroperation is called you may keep the value of last update as a variable. When first operation (incrementation) is called you just see if the value you try to increment is larger than the last_update. If it is you just update the value with 1 otherwise you initialize it to last_update + 1. When the second operation is called you just update last_updateto current_max. And finally, when you are finished and try to return the final values you again compare each value to last_update. If it is greater you just keep the value otherwise you return last_update

想象一下，数组的每个元素都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;
    }
}

回答by andredor

The problem is that when you get lots of max_counteroperations you get lots of calls to Arrays.fillwhich makes your solution slow.

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

You should keep a currentMaxand a currentMin:

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

• When you get a max_counteryou just set currentMin = currentMax.
• If you get another value, let's call it i:
  • If the value at position i - 1is smaller or equal to currentMinyou set it to currentMin + 1.
  • Otherwise you increment it.

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

At the end just go through the counters array again and set everything less than currentMinto currentMin.

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

回答by moda

Another solution that I have developed and might be worth considering: http://codility.com/demo/results/demoM658NU-DYR/

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

回答by Piyush Beli

This is the 100% solution of this question.

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

回答by JonathanC

  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;
}

回答by sammy333

Hera is my AC Java solution. The idea is the same as @Inwvr explained:

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;
    }

回答by moxi

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

我正在添加另一个带有一些测试用例的 Java 100 解决方案，它们很有帮助。

// 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;
   }
}

回答by Eric Kittell

I just got 100 in PHP with some help from the above

在上面的帮助下，我在 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;


}

回答by piyush121

Here is my C++ solution which got 100 on codility. The concept is same as explained above.

这是我的 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;
}

回答by GrayMouser

This is another C++ solution to the problem.

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

The rationale is always the same.

道理总是一样的。

1. Avoid to set to max counter all the counter upon instruction two, as this would bring the complexity to O(N*M).
2. Wait until we get another operation code on a single counter.
3. At this point the algorithm remembers whether it had met a max_counter and set the counter value consequently.

1. 避免在指令 2 时将所有计数器设置为 max counter，因为这会使复杂度变为 O(N*M)。
2. 等到我们在单个计数器上获得另一个操作代码。
3. 此时，算法会记住它是否遇到了 max_counter 并因此设置了计数器值。

Here the code:

这里的代码：

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;
}