Sortiere ein Array, dessen Elemente von 1 bis n reichen, wobei ein Element fehlt und eines wiederholt wird

Question

Ich muss dieses Array in O (n) time und O (1) space sortieren.

Ich weiß, wie man ein Array in O (n) sortiert, aber das funktioniert nicht mit fehlenden und wiederholten Zahlen. Wenn ich die wiederholten und fehlenden Zahlen zuerst finde (es kann in O (n) gemacht werden) und dann sortieren, erscheint das teuer.

static void sort(int[] arr) 
{ 
    for(int i=0;i<arr.length;i++) 
    { 
     if(i>=arr.length) 
      break; 
     if(arr[i]-1 == i) 
      continue; 
     else 
     { 
     while(arr[i]-1 != i) 
     { 
      int temp = arr[arr[i]-1]; 
      arr[arr[i]-1] = arr[i]; 
      arr[i] = temp; 
     } 
     } 
    } 
} 

Answer 1

void sort() { 
    for (int i = 1; i <= N; ++i) { 
    while (a[i] != a[a[i]]) { 
     std::swap(a[i], a[a[i]]); 
    } 
    } 

    for (int i = 1; i <= N; ++i) { 
    if (a[i] == i) continue; 
    for (int j = a[i] - 1; j >= i; --j) a[j] = j + 1; 
    for (int j = a[i] + 1; j <= i; ++j) a[j] = j - 1; 
    break; 
    } 
} 

Erläuterung: Lasst uns m die fehlende Zahl bezeichnen und d die duplizierten Nummer

• Bitte beachten Sie, in der while Schleife ist die Abbruchbedingung a[i] != a[a[i]], die sowohl a[i] == i abdeckt und a[i] ist ein Duplikat.
• Nach dem ersten für, jedes nicht-Duplikat Nummer i ist 1-2 Mal aufgetreten und in die i-th Position des Arrays höchstens einmal verschoben.
• Die erste Zahl gefunden wird d auf d-ten Stellung bewegt wird, höchstens 1 Zeit

• Die zweiten D herum höchstens N-1-mal bewegt werden und enden in m-ten Position, weil jeder anderen i- up ten Steckplatz ist besetzt mit Nummer i

• Die second outer for lokalisieren die erste, wo ich [i]! = ich. Die einzigen i erfüllt die i = m

• Die 2 inner fors Griff 2 Fälle, in denen m < d und m > d jeweils

vollständige Umsetzung bei http://ideone.com/VDuLka

Answer 2

Nach

  int temp = arr[arr[i]-1]; 

eine Prüfung auf doppelte in der Schleife hinzu:

  if((temp-1) == i){ // found duplicate 
       ... 
      } else { 
       arr[arr[i]-1] = arr[i]; 
       arr[i] = temp; 
      } 

Sehen Sie, wenn Sie den Rest des Codes herausfinden können.

Answer 3

Zuerst müssen Sie fehlende und wiederholte Nummern finden. Sie tun dies, indem folgendes Gleichungssystem gelöst:

Linke Summen berechnet werden gleichzeitig durch einen Durchlauf über Array zu machen. Richtige Summen sind noch einfacher - Sie können Formeln für die arithmetische Progression verwenden, um Schleifen zu vermeiden. So, jetzt haben Sie ein System von zwei Gleichungen mit zwei Unbekannten: fehlende Nummer m und wiederholte Nummer r. Löse es.

Als nächstes "sortieren" Sie das Array, indem Sie es mit den Zahlen 1 bis n von links nach rechts ausfüllen, indem Sie m auslassen und r duplizieren. Somit erfordert der Gesamtalgorithmus nur zwei Durchgänge über das Array.