java codility Max-Zähler

Question

Ich habe versucht, die folgenden Aufgaben zu lösen:

Sie sind N-Zähler gegeben, zunächst auf 0 gesetzt, und Sie haben zwei mögliche Operationen auf ihnen:

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

A Nicht leeres nullindiziertes Array A von M ganzen Zahlen ist gegeben. Diese Anordnung stellt aufeinander folgende Operationen:

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. 

Zum Beispiel gegebene ganze Zahl N = 5 und Array-A, so dass:

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

die Werte des Zählers nach jedem aufeinanderfolgenden Vorgang werden:

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

Ziel ist es, den Wert jedes Zählers nach allen Operationen zu berechnen.

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

Schreiben eine Funktion:

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

, die, da eine ganze Zahl N und ein nicht-leere Null indiziertes Array A, bestehend aus M ganzen Zahlen sind, eine Folge von ganzen Zahlen gibt die Werte des Zählers repräsentierten .

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

Zum Beispiel gegeben:

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

die Funktion zurückgeben sollte [3, 2, 2, 4, 2], wie oben erklärt

die Sequenz als zurückgegeben werden sollte.

davon ausgehen, dass:

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

Komplexität:

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

Elemente des Eingabe-Arrays geändert werden kann.

Hier ist meine Lösung:

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

Hier ist der Code Bewertung: https://codility.com/demo/results/demo6AKE5C-EJQ/

Können Sie mir einen Tipp geben, was mit dieser Lösung ist falsch?

Answer 1

Das Problem kommt mit diesem Stück Code:

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

vorstellen, dass jedes Element des Arrays mit dem Wert AN+1 initialisiert wurde. Da der Funktionsaufruf Arrays.fill(countersArray, currentMax) eine Zeitkomplexität von O(N) hat, wird Ihr Algorithmus insgesamt eine Zeitkomplexität von O(M * N) haben. Ein Weg, um dies zu beheben, denke ich, anstatt das gesamte Array A explizit zu aktualisieren, wenn die max_counter Operation aufgerufen wird, können Sie den Wert der letzten Aktualisierung als Variable beibehalten. Wenn die erste Operation (Inkrementierung) aufgerufen wird, sehen Sie, ob der Wert, den Sie zu erhöhen versuchen, größer ist als last_update. Wenn es Sie nur aktualisieren Sie den Wert mit 1 andernfalls initialisieren Sie es auf last_update + 1. Wenn die zweite Operation aufgerufen wird, aktualisieren Sie einfach last_update zu current_max. Und schließlich, wenn Sie fertig sind und versuchen, die endgültigen Werte zurückzugeben, vergleichen Sie jeden Wert erneut mit last_update. Wenn es größer Sie nur den Wert halten andernfalls kehren Sie zurück 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

Das Problem ist, dass, wenn Sie viele max_counter Operationen erhalten Sie viele Anrufe an Arrays.fill bekommen, die Ihre Lösung langsam macht.

Sie sollten currentMin eine currentMax und halten:

• Wenn Sie eine max_counter erhalten Sie setzen nur currentMin = currentMax.
• Wenn Sie einen anderen Wert zu erhalten, nennen wir es i:
  • Wenn der Wert an der Position i - 1 kleiner oder gleich ist currentMin Sie es currentMin + 1 gesetzt.
  • Andernfalls erhöhen Sie es.

Am Ende durch die Zähler-Array gehen Sie einfach wieder und setzen alles weniger als currentMin zu currentMin.

Answer 3

andere Lösung, die ich entwickelt habe, und vielleicht eine Überlegung wert: http://codility.com/demo/results/demoM658NU-DYR/

Answer 4

Dies ist die 100% ige Lösung dieser Frage.

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

Answer 5

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

Answer 6

Hera ist meine AC Java-Lösung. Die Idee ist die gleiche wie @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; 
    } 

Answer 7

Ich bin eine weitere Java 100-Lösung mit einigen Testfällen, die sie hilfreich sind.

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

Answer 8

Ich habe gerade 100 in PHP mit etwas Hilfe von oben

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; 


} 

Answer 9

Hier meine C++ Lösung, die 100 auf codility bekam. Das Konzept ist das gleiche wie oben erläutert.

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

Answer 10

Dies ist eine weitere C++ - Lösung für das Problem.

Die Begründung ist immer gleich.

1. Vermeiden Sie, auf Zähler zwei alle Zähler auf den Höchstwert zu setzen, da dies die Komplexität auf O (N * M) bringen würde.
2. Warten Sie, bis wir einen anderen Operationscode auf einem einzelnen Zähler erhalten haben.
3. An diesem Punkt merkt sich der Algorithmus, ob er einen max_counter getroffen und den Zählerwert entsprechend gesetzt hat.

Hier ist der 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; 
} 

Answer 11

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

Answer 12

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

Answer 13

hier ist mein Code, aber seine 88% Ursache es dauert 3,80 sec für 10000 Elemente anstelle von 2,20

Klasse Lösung {

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

} 

}

Answer 14

Arrays.fill() Aufruf innerhalb Array interation macht das Programm O (N^2)

Here ist eine mögliche Lösung, die O (M + N) Laufzeit hat.

Die Idee ist -

1. Für die zweite Operation, Spur von max-Wert halten, die durch Erhöhung erreicht wird, das ist unser Grundwert bis zur aktuellen Iteration, können keine Werte nicht weniger als diese .

2. Bei der ersten Operation wird der Wert vor der Inkrementierung auf den Basiswert zurückgesetzt.

   public static int [] Lösung (int N, int [] A) { int Zähler [] = 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; 
   

   }

Answer 15

Nach meiner Lösung in 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; 
}