java - Java codility Max-Counters

Question

私は以下のタスクを解決しようとしています:

最初は 0 に設定された N 個のカウンターが与えられ、それらに対して 2 つの操作が可能です。

    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 14 · Accepted Answer

問題は、多くのmax_counter操作を取得すると、多くの呼び出しがArrays.fill発生し、ソリューションが遅くなることです。

currentMaxaと aを保持する必要がありcurrentMinます。

を取得しmax_counterたら、設定したばかりですcurrentMin = currentMax。
別の値を取得したら、それを呼び出しましょうi:
- position の値i - 1がより小さいか等しい場合は、currentMinに設定しますcurrentMin + 1。
- それ以外の場合は、インクリメントします。

currentMin最後に、もう一度 counters 配列を調べて、 to未満のすべてを設定しますcurrentMin。

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 6 · Accepted Answer

私が開発した、検討する価値のある別のソリューション: http://codility.com/demo/results/demoM658NU-DYR/

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

Arrays.fill()配列相互作用内での呼び出しにより、プログラムは O(N^2) になります

O(M+N) ランタイムを持つ可能なソリューションを次に示します。

アイデアは -

2 番目の操作では、インクリメントによって達成される最大値を追跡します。これは、現在の反復までの基本値であり、これよりも小さい値にすることはできません。

最初の操作では、インクリメントの前に必要に応じて値をベース値にリセットします。

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

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

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

これは、この問題に対する別の C++ ソリューションです。

理屈はいつも同じ。

命令 2 ですべてのカウンターを最大カウンターに設定しないでください。これにより、複雑さが O(N*M) になる可能性があります。
1 つのカウンターで別の操作コードを取得するまで待ちます。
この時点で、アルゴリズムは 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

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

これは、100% スコアの C++ ソリューションです。

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

java - Java codility Max-Counters

34 に答える 34

Related

Reference