die kleinste und die zweiten kleinste Zahl in einer Anordnung von acht Zahlen mit nur 9 Vergleichen

Question

Dies ist ein Interview Frage, die ich beantworten musste. Nun, eigentlich Freunde, aber er hat mich gefragt, und ich wusste auch nicht die Antwort. Daher frage ich hier:

Angesichts einer Reihe von 8 ganzen Zahlen, finden Sie die kleinste und die zweitkleinste ganze Zahl mit nur 9 Vergleiche. Genauer gesagt in n+log(n)-2 Zeit.

Ich bin sicher, beachten Sie, wie Sie es nur 9 Vergleiche mit tun können. So nah bin ich dran. (10 Vergleiche)

public class Comp { 
    static int[] nums = new int[]{9, 4, 5, 3, 2, 7, 6, 1}; 
    static int compcount = 0; 

    //int[] is nums[] array 
    public static int[] twoLeast(int[] a){ 
     int min1 = a[0]; //Prospective lowest number 
     int min2 = a[1]; //Prospective second lowest number 

     if(isLessThan(min2, min1)){ 
      min1 = a[1]; 
      min2 = a[0]; 
     } 

     for(int i=2; i<a.length;i++){ 
      if(isLessThan(a[i], min1)){ 
       min2 = min1; 
       min1 = a[i]; 
      }else if(isLessThan(a[i], min2)){ 
       min2 = a[i]; 
      } 
     } 

     return new int[]{min1, min2}; 
    } 

    public static boolean isLessThan(int num1, int num2){ 
     compcount++; 
     return num1 < num2; 
    } 
} 

Hier habe ich eine Funktion isLessThan() Überblick über die Anzahl der Vergleiche zu halten. Auch dies macht 10 Vergleiche. Wie ist es möglich, dies in 9 Vergleichen zu tun? Oder in n+log(n)-2 Zeit?

PS: Ich habe es in Java implementiert, aber es kann als Hinweis jede Sprache

Answer 1

Ein Weg, um die Lösung zu denken, ist dies wie ein Tennis knock-off Wettkampfserie. Angenommen, jede Nummer entspricht einem Spieler. Paar aus den Zahlen und lassen jedes Spiel innerhalb eines Paares auf einen Vergleich zwischen den Zahlen entsprechen:

Spiele: (a1,a2), (a3, a4), (a5, a6), (a7, a8)

Sieger: a12, a34, a56, a78

Spiele: (a12, a34), (a56, a78)

Sieger: a1234, a5678

Spiel: (a1234, a5678)

Gewinner: a12345678

Anzahl der Spiele = 7 ==>(n - 1)

Die zweitbeste besiegt wurden von den Siegern nur werden. Angenommen, a3 ist der Gewinner. Dann zweite das beste wird a4, a12 oder a5678 sein.

Spiele: (a4, a12)

Gewinner: a412

Spiele: a(412, 5678)

Gewinner: a4125678

So haben wir 2 Spiele für die zweitbeste ==>(lg(n) - 1)

Daher Anzahl der Spiele = 7 + 2 = 9 = (n + lg(n) - 2)

Dies ist einfacher, die über den Wettbewerb um einen Baum zu visualisieren:

   a12345678 
      /  \ 
      /   \ 
      /   \ 
     /    \ 
     a1234   a5678 
    / \   / \ 
    /  \  / \ 
    a12  a34  a56  a78 
/ \ / \ / \ /\ 
a1  a2 a3 a4 a5 a6 a7 a8 

Wenn a3 der Gewinner ist, haben wir:

    a3 
        | 
       /----|----\ 
      /   \ 
      /   \ 
     /    \ 
      a3 >==========> a5678 
    / \   / \ 
    /  \  / \ 
    a12 <====< a3  a56  a78 
/ \ / \ / \ /\ 
a1  a2 a3 ->a4 a5 a6 a7 a8 

Grundsätzlich ist der ultimative Gewinner a3 wird ein durchlaufen haben Weg vom Blatt zur Wurzel (lg(n) -1). Auf seinem Weg hat er den zweitbesten Spieler besiegt, der einer von {a4, a12, a5678} ist. Wir können also herausfinden, wer der Zweitbeste ist, indem wir den Maximalwert auf dem Weg vom Gewinner betrachten, der wie beschrieben ist.

Answer 2

sein, eine Eliminations Turnier Halterung für die Elemente des Arrays zu spielen einzurichten Die größte Zahl im Array wird die gewinnen. Turnier, und Sie brauchen nur n - 1 Vergleiche, wenn n eine Potenz von zwei ist.

Das zweitgrößte Element darf nur nur zu dem größten, und im Turnier verloren haben, das größte Element schlagen n andere Elemente loggen sein. Spielen Sie ein zweites Ausscheidungsturnier nur dieser Elemente, um das größte Element dort zu finden, das log n - 1 Vergleiche erfordert.

Insgesamt nur n + log n - 2 Gesamt Vergleiche benötigt. Alles, was übrig bleibt, ist es zu codieren.

Hoffe, das hilft!