Optimieren der doppelten Iteration über Arrays

Question

Ich habe den folgenden Code, den ich für ein Übungsproblem in einem Codierungswettbewerb geschrieben habe, aber wenn ich es ausführe, gehe ich mit der Zeit. Der Hauptschuldige (ich vermute) ist die doppelte for-Schleife, die in O (n^2) läuft. Gibt es eine Möglichkeit, diesen Code zu optimieren? Ich habe versucht, mit Memoization zu spielen, aber ich kann nicht herausfinden, wie es geht.

for (i=n;i>0;i--){ 
    int index = linearSearch(seq,i,n); 
    int height = bricks[index]; 
    for (j=0;j<n;j++){ 
     if (j != index){ 
      if (bricks[j] >= height){ 
       while(bricks[j]>=height){ 
        bricks[j]--; 
        count++; 
       } 

       if(bricks[j] < 0){ 
        printf("-1\n"); 
        return 0; 
       } 

      } 
     } 
    } 

    bricks[index] = 0; 
    seq[index] = 0; 
} 

Answer 1

Ich bin von dem Ziel des entsandten Code-Schnipsel nicht sicher, aber die folgenden vorgeschlagenen Code mit der Ausführungsdauer helfen können:

for (i=n; i>0; i--) 
{ 
    int index = linearSearch(seq,i,n); 
    int height = bricks[index]; 

    for (j=0; j<n ; j++) 
    { 
     if(j != index) 
     { 
      if(bricks[j] >= height) 
      { 
       count += bricks[j] - height; 
       bricks[j] -= bricks[j] - height; 
      } 
     } 
    } 

    bricks[index] = 0; 
    seq[index] = 0; 
}