Sortierung 100 eindeutige Nummern von 40bytes Speicher mit

Question

Ich habe ein gutes Programmierproblem gefragt worden:

Im Eingang I 100 eindeutige Nummern 0-255 (1 Byte) habe. Ich kann nur eine Nummer auf einmal und nur einmal lesen. Ich habe 40 Bytes Speicher, die ich benutzen kann. Das Ziel ist, alle Zahlen zu sortieren und sie in der Ausgabe zu drucken. Ich bin mir sicher, dass die Einzigartigkeit der Zahlen sehr wichtig ist.

Irgendwelche Ideen?

Answer 1

32 Bytes ergeben 256 Bits, gerade genug, um eine Bitmap zu erhalten, welche der 256 möglichen Bytewerte in der Eingabe zu sehen sind. Ein zusätzliches Byte wird zum Speichern des Eingabewerts verwendet. Lesen Sie jeden Wert, markieren Sie ihn in der Bitmap und verwerfen Sie ihn. Sobald Sie alle 100 Eingabewerte gelesen haben, schreiben Sie einfach den Wert, der mit den Bits in der Bitmap verknüpft ist.

Dann fragen Sie, was Sie mit den anderen 7 Bytes tun sollen :)

Answer 2

Da Ihre Zahlen eindeutig sind und nur 1 Byte lang sind, müssen sie zwischen 0 und 255 liegen. Behandeln Sie Ihre 40 Byte Speicher als langen Bitvektor. Wenn Sie jede Zahl lesen, stellen Sie das entsprechende Bit in diesem 320-Bit-Vektor ein. Wenn Sie mit dem Lesen der Eingabe fertig sind, drehen Sie sich um und scannen Sie durch diesen Bitvektor, wobei Sie die Nummer für jedes gesetzte Bit ausgeben.

In Reaktion auf @ JavaNewb, hier ist mehr Details. Erstens, da ein Byte 8 Bits enthält, kann es nur einen von 256 möglichen Werten annehmen, nämlich 0 bis 255. Bewaffnet mit dieser kleinen Tatsache, schauen Sie sich das 40-Byte-Speicherarray an, das Sie haben. Dieses Array hat 40 Bytes * 8 Bits/Byte = 320 Bits. Da das Problem angibt, dass jede der 100 1-Byte-Nummern eindeutig ist, wissen Sie, dass Sie eine bestimmte Zahl (die von 0 bis 255 reichen kann) höchstens einmal sehen. Jedes Mal, wenn Sie eine Nummer sehen, setzen Sie das entsprechende Bit in dem 40-Byte-Array. Zum Beispiel, wenn Sie die Zahl 50 treffen, setzen Sie Bit Nummer 2 in Byte Nummer 6. Eine Nummer N entspricht Bit N%8 in Byte N/8. Sie werden garantiert nie ein gesetztes Bit in diesem Array finden, da dies die Existenz von Duplikaten in den 100 Zahlen implizieren würde. Nachdem Sie alle Zahlen eingelesen haben, sehen Sie sich das 40-Byte-Array an. Jedes Bit, das in diesem Array gesetzt ist, entspricht einer der 100 Zahlen, die Sie eingelesen haben. Indem Sie dieses 40-Byte-Array vom 0. Bit im 0. Byte bis zum 7. Bit im 31. Byte durchlaufen, erhalten Sie:

1. Capturing alle Zahlen, die in
2. gelesen wurden Beobachten sie in einer sortierten Reihenfolge

alles, was Sie jetzt tun müssen, ist Druck die Zahlen zu den gesetzten Bits entsprechen, wie Sie die 40- Traverse Byte-Array.