Ich habe ein Array A und ein anderes Array B. Wie entferne ich Elemente in A von B und was wäre die Laufzeit des Algorithmus? Duplikate erlaubt.Entfernen eines Array-Elements von einem anderen Array-Algorithmus
Vielen Dank im Voraus!
Ein einzelnes Array hat eine Worst-Case-Laufzeit von O (N) und zwei Arrays haben typischerweise eine Array-Laufzeit von O (N^2). Sie können ein Systemereignis oder eine Benutzereingabe verwenden, um ein Element zu entfernen, z. Bei einem String-Array können Sie den Benutzer bitten, die zu entfernenden Elemente auszuwählen und eine leere Zeichenfolge in diesen Indizes zuzuordnen, oder Sie können ein Systemereignis verwenden, um die erforderlichen Elemente zu entfernen.
Die Laufzeit hängt vollständig von Ihrer Implementierung ab.
Sortieren A und die Laufzeit könnte O ((A + B) log A) sein.
Wenn die Werte in A und B können gehasht werden, könnte die Laufzeit sein O (A + B)
Wenn Sie kümmern sich nicht um die Array-Elemente ihre relative Reihenfolge beibehalten wird, ein Element zu entfernen, ist O (1). Tauschen Sie einfach das Element, das Sie entfernen möchten, mit dem letzten Element und verringern Sie Ihre Größe.
Es ist möglich, die Reihenfolge der Elemente mit der gleichen Komplexität beizubehalten - nur Duplikate zu verpassen (sie zu zählen) und das gute Element von der i-ten Position in "A [i - dupcount]" zu verschieben – MBo
Das Entfernen ist implementierungsabhängig. Sie haben nicht einmal eine Sprache für die Implementierung angegeben. Auf der Algorithmusebene ist es lediglich die Menge "B-A". Die Laufzeit ist abhängig von der Hardware, der Sprache, der Implementierung eines Arrays, der Hardware, auf der Sie arbeiten, der Array-Größe ... – Prune
Welchen Algorithmus möchten Sie verwenden? Was hast du bisher versucht? – ilim