Trova il numero più piccolo e il secondo più piccolo in un array di 8 numeri con solo 9 confronti

Question

Questa è una domanda di intervista che dovevo rispondere. Beh, in effetti un amico, ma lui mi ha chiesto e non sapevo nemmeno la risposta. Quindi sto chiedendo qui:

Dato un array di 8 numeri interi, trovare il più piccolo e il secondo più piccolo intero utilizzando solo 9 confronti. Più precisamente nel tempo n+log(n)-2.

Sono sicuro che come è possibile farlo utilizzando solo 9 confronti. È così vicino che ci sono arrivato. (10) i confronti

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

Qui mi hanno una funzione isLessThan() per tenere traccia del numero di confronti. Ancora, questo fa 10 confronti. Com'è possibile farlo in 9 confronti. O nel tempo n+log(n)-2?

PS: ho implementato in Java, ma può essere qualsiasi lingua

Answer 1

Un modo per pensare alla soluzione è che questa è una serie di competizioni sportive. Supponiamo che ogni numero corrisponda a un giocatore. Coppia fuori i numeri e lasciare che ogni gioco corrisponde ad un confronto tra i numeri all'interno di una coppia:

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

Vincitori: a12, a34, a56, a78

Games: , (a56, a78)

Vincitori: a1234, a5678

Gioco: (a1234, a5678)

Vincitore: a12345678

Numero di giochi = 7 ==>(n - 1)

Il secondo miglior saranno stati sconfitti solo dal vincitore. Supponiamo che a3 sia il vincitore. Quindi il secondo migliore sarà a4, a12 o a5678.

Giochi: (a4, a12)

Vincitore: a412

Giochi: a(412, 5678)

Vincitore: a4125678

Così abbiamo 2 giochi per il secondo miglior ==>(lg(n) - 1)

Quindi numero di partite = 7 + 2 = 9 = (n + lg(n) - 2)

Questo è più facile da visualizzare concorso sopra un albero:

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

Se a3 è il vincitore, abbiamo:

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

Fondamentalmente il vincitore finale a3 avranno attraversato una percorso dalla foglia alla radice (lg(n) -1). Nel suo percorso, avrà sconfitto il secondo miglior giocatore, che è uno di {a4, a12, a5678}. Quindi possiamo solo capire chi è il secondo migliore guardando il massimo nel percorso a parte il vincitore che è come descritto.

Answer 2

come un suggerimento, impostare una staffa torneo ad eliminazione per gli elementi della matrice di giocare nel più grande numero di nella matrice vincerà il. torneo, e avrai solo bisogno di n - 1 confronti se n è una potenza di due.

L'elemento secondo più grande deve aver perso solo il più grande, e nel torneo l'elemento più grande ha battuto solo altri elementi. Gioca un torneo di seconda eliminazione di solo quegli elementi per trovare l'elemento più grande lì, che richiede il confronto log n-1.

Complessivamente, solo n + log n - sono necessari 2 confronti totali. Tutto ciò che rimane è di codificarlo.

Spero che questo aiuti!