Was ist falsch mit dieser Lösung für die Max-Zähler codility Herausforderung

Überprüfen Sie dieses (python, bekommen 100 score):

Das Geheimnis ist, nicht auf " alle aktualisieren der Zähler jedes mal, wenn Sie die Anweisung zu stoßen, Sie alle bis auf einen neuen Minimalwert. Dies erfordert eine operation mit jeder Zähler bei jeder Gelegenheit, und das ist der Unterschied zwischen einem ~60% Punktzahl und eine 100% - score.

Stattdessen vermeiden diese Treffer durch verfolgen der aktuellen minimum-und maximum-Werte; verwenden und aktualisieren Sie für jeden Zähler die Sie besuchen.

Dann, nach all den Anweisungen verarbeitet werden, weil es vielleicht Schalter, die noch nicht berührt worden ist, mit Ihren eigenen persönlichen update seit dem letzten update-alle Anweisungen, pass über den Tresen selbst und gewährleisten, dass Sie mindestens Wert.

def solution(N, A):
    res = [0] * N
    max_val = 0
    last_update = 0
    n1 = N+1
    for i in A:
        if i < n1:
            if res[i-1] < last_update:
                res[i-1] = last_update

            res[i-1]+=1

            if res[i-1] > max_val:
                max_val = res[i-1]
        else:
            last_update = max_val

    for i in xrange(len(res)):
        if res[i] < last_update:
            res[i] = last_update

    return res

http://codility.com/demo/results/demoF3AMPT-FVN/

Betrachten Sie diese 100/100-Lösung in Ruby:

# Algorithm:
#
# * Maintain a maximum value.
# * For each `increase(X)` command update respective counter.
# * For each `max_counter` command save the current max as `set_max` for later use.
# * Once the loop is over, make an adjustment pass to set all values less than `set_max` to `set_max`.
def solution(n, commands)
  max = set_max = 0
  counters = Array.new(n, 0)

  commands.each do |cmd|
    if cmd <= n
      # This is an `increase(X)` command.
      value = [counters[cmd - 1], set_max].max + 1
      counters[cmd - 1] = value
      max = [value, max].max
    else
      # This is a `max_counter` command.
      # Just update `set_max`.
      set_max = max
    end
  end

  # Finalize -- set counters less than `set_max` to `set_max`.
  counters.map! {|value| [value, set_max].max}

  # Result.
  counters
end

#--------------------------------------- Tests

def test
  sets = []
  sets << ["1", [1], 1, [1]]
  sets << ["sample", [3, 2, 2, 4, 2], 5, [3, 4, 4, 6, 1, 4, 4]]

  sets.each do |name, expected, n, commands|
    out = solution(n, commands)
    raise "FAILURE at test #{name.inspect}: #{out.inspect} != #{expected.inspect}" if out != expected
  end

  puts "SUCCESS: All tests passed"
end

Meine python version nur 66 Punkte erzielt, da es ein wenig zu langsam für die späteren tests.

def solution(N, A):
    counters = [0 for x in range(N)]
    for elem in A:
        if elem > N:
            cmax = max(counters)
            counters = [cmax for x in range(N)]
        else:
            counters[elem-1] += 1
    return counters

Habe ich 77% mit dieser Lösung in java:

Kann mir jemand empfehlen die 100% Lösung ?

 import java.util.Arrays;
 class Solution {
 public int[] solution(int N, int[] A) {

 int maxCounter=0;
 int[] B=new int[N];

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

 if(A[i]==N+1){
 setMaximum(B, maxCounter);
 }
 else{
 B[A[i]-1]++;               
 if(maxCounter<B[A[i]-1]){
 maxCounter=B[A[i]-1];
 }

 }
 }
 return B;
 }

 void setMaximum(int[] B,int maxValue){
 for(int i=0;i<B.length;i++){
 B[i]=maxValue;
 }

 }
 }

Javascript 100/100

JS:

function solution(N, A) {
    
    var j, len = A.length, lastBase = 0, max = 0, 
        counters = [], n1 = N+1;

    for(j=0; j<N; j+=1){
        counters[j]=0; //initArray
    }
    
    for(j=0; j < len; j+=1){
        if(A[j]<n1){
            if(counters[A[j]-1] < lastBase) {
                counters[A[j]-1] = lastBase;
            }
            counters[A[j]-1] += 1;
            if(max < counters[A[j]-1]) {
                max = counters[A[j]-1];
            }
        } else {
            lastBase = max;
        }
    }
    
    for(j=0; j<N; j+=1){
        if(counters[j] < lastBase) {
            counters[j] = lastBase;
        }
    }
    
    return counters;
    
}

Java solution -->


    public int[] solution(int N, int[] A) {
        // write your code in Java SE 8
        int[] counter = new int[N];
        int maxCounter = 0;
        int pos;
        int last_max=0;
        for (int i = 0; i < A.length; i++) {
            if (A[i] <= N) {
                pos = A[i];

                if (counter[pos - 1] < last_max)
                    counter[pos - 1] = last_max;
                counter[pos - 1] += 1;

                if (maxCounter < counter[pos - 1])
                    maxCounter = counter[pos - 1];
            }
            else{
                last_max=maxCounter;
            }
        }

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

C# - a 100/100 Lösung

public int[] solution(int N, int[] A) {
    // write your code in C# 6.0 with .NET 4.5 (Mono)
    int[] counter = new int[N];
    int maxValue = 0;
    int minValue = 0;
    for(int i=0;i<A.Length;i++)
    {
        //less than or equal to length N
        if(A[i] <= N)
        {
            if(counter[A[i] - 1] < minValue)
            {
                counter[A[i] - 1] = minValue;
            }
            counter[A[i] - 1] += 1;
            if(counter[A[i] - 1] > maxValue)
            {
                maxValue = counter[A[i] - 1];
            }
        }
        else if(A[i] == N+1)
        {
            minValue = maxValue;
        }
    }
    for(int j=0;j<counter.Length;j++)
    {
        if(counter[j] < minValue)
        {
            counter[j] = minValue;
        }
    }
    return counter;
}