Neuzuordnen eines Arrays mit O (1) Leerzeichen

Es tut mir leid, dass ich nicht sicher bin, welcher Typ dieses Problem genannt wird, nennen wir es einfach "Remapping", wie folgt beschrieben: Gegeben ein Ziel-Char-Array, sagen A [], musst du A direkt manipulieren. Und ein Remapping-Index-Array-Index [], der Indizes enthält, in denen der Wert neu zugewiesen werden sollte. Zum Beispiel, gegeben A [] = {a, b, c, d, e}, Index [] = {2,4,3,0,1}. Also Index [0] = 2, was bedeutet, dass nach der Manipulation der Wert einmal in A [0] A [2] sein muss, A [1] in A [4] usw. Ich weiß, dass dieses Problem extrem ist einfach, wenn wir ein anderes Array haben:Neuzuordnen eines Arrays mit O (1) Leerzeichen

vector<char> myarr = vector<char>(A.size()); 
for (int i = 0; i < myarr.size(); i++) 
    myarr[i] = A[index[i]]; 

// myarr is the answer.

Aber was soll ich tun, wenn ich nur O (1) Raum habe? Vielen Dank für Ihre Meinung.

Oh btw, korrigiert mich, wenn ich irgendwelche Fehler in der Grammatik haben. "P

Quelle

2016-04-12 Shih-Chan Huang

Nun, ein C++ Array muss eine konstante Größe bei der Kompilierung bekannt haben. Jedes andere Array der gleichen Größe hat folglich auch eine konstante Größe. Was bedeutet, dass Sie _ O (1) Speicher verwenden. Also ... wenn du schlau bist ...: – Damon

TIPP: Das Problem, das du hast, ist, was du mit dem alten Wert von 'myArr [2]' (4) machen sollst, nachdem du 'myArr [2] = getan hast 2'. Wo würdest du das 4 schreiben, damit es dir keinen zusätzlichen Platz kostet? Beachten Sie, dass O (1) nicht nur eine Variable bedeutet, sondern eine konstante Anzahl von Variablen. – SJuan76

Im Allgemeinen ist dies nicht möglich. Irgendwelche Einschränkungen? –

Das Problem durch Vertauschen ein Wertepaar mit konstantem Speicher, um gelöst werden kann, um das Ergebnis an Ort und Stelle zu erzeugen zwar keine direkte duplizieren, wird das Problem in this question diskutiert

Quelle

2016-04-12 12:46:19 Codor

danke, mein Herr. Das ist die genaue Antwort, nach der ich suche, obwohl die Funktion seines Indice-Arrays einen kleinen Unterschied zu meinem hat. –

Sie es tun können zwei Variablen, hier eine grobe Skizze des Algorithmus ist.

for i=0:n 
    t_index = i 
    swap_index = index[t_index] 
    if index[i]!=-1: 
     while t_index!=swap_index 
      SWAP(index[t_index],index[swap_index]) 
      index[t_index] = -1 
      t_index = getIndexOfValue(indexe, t_index)

die Implementierung von SWAP, die zwei Werte Swaps und getIndexOfValue, die den Index eines Wertes von einem Array zurückgibt, sind hier nicht abgedeckt; aber sie sollten einfach zu verstehen sein

Die Idee hier ist es, den Index des Werts zu verfolgen, der ausgetauscht wurde. Nach dem ersten Austausch endet der A [0] in A [2], also müssen Sie herausfinden, wo der Wert am Index 0 im ursprünglichen Array enden muss, und ihn in Position tauschen ..... und bald.

es auf dem Papier soll Ihnen helfen, das ganze Bild sehen, wenn Sie in Schwierigkeiten geraten

Quelle

2016-04-12 13:42:47 Pandrei

Neuzuordnen eines Arrays mit O (1) Leerzeichen

Antwort

Verwandte Themen