6
votes

Trier la matrice par ordre selon un autre tableau

J'ai un objet qui est renvoyé d'une base de données comme ceci: [{id: 1}, {id: 2}, {id: 3}] . J'ai un autre tableau qui spécifiait la commande que le premier tableau doit être trié, comme celui-ci: [2,3,1] .

Je recherche une méthode ou un algorithme pouvant prendre dans ces deux tableaux et retourner [{id: 2}, {id: 3}, {id: 1}] . Idéalement, il devrait être en quelque sorte efficace et non carré.


                        
                        
                            
                                                                    javascript
                                                                    algorithm
                                                                    sorting
                                                            
                        
                                                    
                            
                            
                                0 commentaires



                                    
                    6 Réponses :
                    
                                            
                            
                                
                                    0
 votes
                                
                            
                            
                                
                                     à ma compréhension, le tri n'est pas nécessaire; Au moins dans votre exemple, la matrice résultante souhaitée peut être générée en temps linéaire comme suit.  xxx  
 ici  résultat  est la sortie souhaitée,  entrée  est votre premier tableau et  commande  le tableau contenant les positions souhaitées.                                  


                                                                    
                                    
                                    
                                        2 commentaires
                                        
                                                                                            
                                                    Cela suppose que le tableau d'origine est déjà trié par les valeurs  id  et ils sont consécutifs.                                                
                                                
                                                                                            
                                                    Vous avez raison, mais l'exemple fourni a ces deux propriétés et il n'est pas indiqué différemment ailleurs qu'ils peuvent être violés.                                                
                                                
                                                                                    
                                    
                                                            

                        

                        
                                            
                            
                                
                                    3
 votes
                                
                            
                            
                                
                                     


    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]));

                                

                                                                    
                                    
                                    
                                        0 commentaires
                                        
                                                                                    
                                    
                                                            
                        
                        
                                            
                            
                                
                                    0
 votes
                                
                            
                            
                                
                                    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])
};

                                

                                                                    
                                    
                                    
                                        2 commentaires
                                        
                                                                                            
                                                    Obj Array ne peut pas être indexé par sortOrder                                                
                                                
                                                                                            
                                                    Mon erreur. Je pensais que la question était la 2e matrice avait les positions du tri et non les valeurs d'identification.                                                
                                                
                                                                                    
                                    
                                                            
                        
                        
                                            
                            
                                
                                    0
 votes
                                
                            
                            
                                
                                     Pourquoi ne pas simplement créer un nouveau tableau et appuyer sur la valeur de la deuxième matrice ?? Corrigez-moi si je me trompe  xxx                                  

                                                                    
                                    
                                    
                                        0 commentaires
                                        
                                                                                    
                                    
                                                            
                        
                        
                                            
                            
                                
                                    1
 votes
                                
                            
                            
                                
                                     Dans votre exemple, les objets sont initialement triés par  ID  code>, ce qui rend la tâche assez facile. Mais si cela n'est pas vrai en général, vous pouvez toujours trier les objets en temps linéaire en fonction de votre matrice de  ID  code>. 
 L'idée est d'abord faire un index qui mappe chaque  ID  code> Valeur à sa position, puis insérer chaque objet dans la position souhaitée en recherchant sa valeur  code>  code> dans l'index. Cela nécessite d'itération sur deux tableaux de longueur  n  code>, entraînant une heure d'exécution globale de  O (n)  code> ou du temps linéaire. Il n'y a pas de temps d'exécution plus rapide asymptotiquement, car il faut du temps linéaire juste pour lire le tableau d'entrée.  P> 
  p> 


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 />');
}

                                

                                                                    
                                    
                                    
                                        0 commentaires
                                        
                                                                                    
                                    
                                                            
                        
                        
                                            
                            
                                
                                    7
 votes
                                
                            
                            
                                
                                     Si vous voulez du temps linéaire, créez d'abord une haquetable à partir du premier tableau, puis choisissez des objets en commandant en boucle le second: 
  p> 


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))

                                

                                                                    
                                    
                                    
                                        0 commentaires