Frage Sortieren Sie das Array nach einem anderen Array


Ich habe ein Objekt, das von einer Datenbank wie folgt zurückgegeben wird: [{id:1},{id:2},{id:3}]. Ich habe ein anderes Array, das die Reihenfolge angibt, in der das erste Array sortiert werden soll: [2,3,1].

Ich suche nach einer Methode oder einem Algorithmus, der diese beiden Arrays aufnehmen und zurückgeben kann [{id:2},{id:3},{id:1}]. Idealerweise sollte es so effizient und nicht quadratisch sein.


6
2017-12-04 09:05


Ursprung


Antworten:


Wenn Sie eine lineare Zeit haben möchten, erstellen Sie zuerst eine Hashtabelle aus dem ersten Array und wählen Sie dann die Elemente in der Reihenfolge aus, in der Sie die zweite Schleife durchlaufen:

data = [{id:5},{id:2},{id:9}]
order = [9,5,2]

hash = {}
data.forEach(function(x) { hash[x.id] = x })

sorted = order.map(function(x) { return hash[x] })

document.write(JSON.stringify(sorted))


6
2017-12-04 09:24



    function sortArrayByOrderArray(arr, orderArray) {
        return arr.sort(function(e1, e2) {
            return orderArray.indexOf(e1.id) - orderArray.indexOf(e2.id);
        });
    }

    console.log(sortArrayByOrderArray([{id:1},{id:2},{id:3}], [2,3,1]));


2
2017-12-04 09:13



In Ihrem Beispiel sind die Objekte zunächst nach sortiert id, was die Aufgabe ziemlich einfach macht. Aber wenn das im Allgemeinen nicht zutrifft, können Sie die Objekte immer noch in linearer Zeit nach Ihrem Array sortieren id Werte.

Die Idee besteht darin, zuerst einen Index zu erstellen, der jede Karte abbildet id Wert auf seine Position, und dann jedes Objekt in die gewünschte Position einfügen, indem Sie nach oben suchen id Wert im Index. Dies erfordert ein Iterieren über zwei Längenarrays n, was zu einer Gesamtlaufzeit von O(n)oder lineare Zeit. Es gibt keine asymptotisch schnellere Laufzeit, da nur lineares Lesen des Eingangsarrays erforderlich ist.

function objectsSortedBy(objects, keyName, sortedKeys) {
  var n = objects.length,
      index = new Array(n);
  for (var i = 0; i < n; ++i) {  // Get the position of each sorted key.
    index[sortedKeys[i]] = i;
  }
  var sorted = new Array(n);
  for (var i = 0; i < n; ++i) {  // Look up each object key in the index.
    sorted[index[objects[i][keyName]]] = objects[i];
  }
  return sorted;
}

var objects = [{id: 'Tweety', animal: 'bird'},
               {id: 'Mickey', animal: 'mouse'},
               {id: 'Sylvester', animal: 'cat'}],
    sortedIds = ['Tweety', 'Mickey', 'Sylvester'];

var sortedObjects = objectsSortedBy(objects, 'id', sortedIds);

// Check the result.
for (var i = 0; i < sortedObjects.length; ++i) {
  document.write('id: '+sortedObjects[i].id+', animal: '+sortedObjects[i].animal+'<br />');
}


1
2017-12-04 09:24



Nach meinem Verständnis ist Sortieren nicht notwendig; Zumindest in Ihrem Beispiel kann das gewünschte resultierende Array in linearer Zeit wie folgt erzeugt werden.

var Result;
for ( var i = 0; i < Input.length; i++ )
{
    Result[i] = Input[Order[i]-1];
}

Hier Result ist die gewünschte Ausgabe, Input ist dein erstes Array und Order das Array enthält die gewünschten Positionen.


0
2017-12-04 09:13



var objArray = [{id:1},{id:2},{id:3}];
var sortOrder = [2,3,1];

var newObjArray = [];
for (i in sortOrder) {
    newObjArray.push(objArray[(sortOrder[i]) - 1])
};

0
2017-12-04 09:15



Warum nicht einfach ein neues Array erstellen und den Wert aus dem zweiten Array in ?? Korrigiere mich, wenn ich falsch liege

array1 = [];
array2 = [2,3,1];

for ( var i = 0; i < array2 .length; i++ )
{
    array1.push({
         id : array2[i]
     })
}

0
2017-12-04 09:20