Ich habe diese Frage auf Reddit gesehen und es wurden keine positiven Lösungen vorgestellt, und ich dachte, es wäre eine perfekte Frage, diese hier zu stellen. Dies war in einem Thread über Interviewfragen:

Schreiben Sie eine Methode, die ein int-Array der Größe m annimmt und (True / False) zurückgibt, wenn das Array aus den Zahlen n ... n + m-1, allen Zahlen in diesem Bereich und nur Zahlen in diesem Bereich besteht. Es ist nicht garantiert, dass das Array sortiert ist. (Zum Beispiel würde {2,3,4} true zurückgeben. {1,3,1} false zurückgeben, {1,2,4} false zurückgeben.

Das Problem, das ich mit diesem Problem hatte, war, dass mein Interviewer mich immer wieder aufforderte, es zu optimieren (schnelleres O (n), weniger Speicher, usw.), bis zu dem Punkt, an dem er behauptete, Sie könnten es in einem Durchgang des Arrays mit einer konstanten Menge von tun Erinnerung. Das habe ich nie herausgefunden.

Bitte geben Sie zusammen mit Ihren Lösungen an, ob sie davon ausgehen, dass das Array eindeutige Elemente enthält. Geben Sie auch an, ob Ihre Lösung davon ausgeht, dass die Sequenz bei 1 beginnt. (Ich habe die Frage geringfügig geändert, um Fälle zuzulassen, in denen es um 2, 3, 4 geht ...)

bearbeiten: Ich bin jetzt der Meinung, dass es keinen Algorithmus mit linearer und konstanter Zeit im Raum gibt, der mit Duplikaten umgeht. Kann jemand dies überprüfen?

Das Duplikat-Problem besteht darin, zu testen, ob das Array Duplikate in O (n) Zeit und O (1) Raum enthält. Wenn dies möglich ist, können Sie einfach zuerst testen. Wenn keine Duplikate vorhanden sind, führen Sie die angegebenen Algorithmen aus. Können Sie also in O (n) Zeit O (1) Raum auf Dupes testen?