Algorithmus: Next Greater Element I (aus dem Leetcode)

Question

Kann mir bitte jemand sagen, was ich bei der Lösung dieses Algorithmus vermisse? Ein Problem, das ich habe, ist, dass meine erste if-Anweisung in der Nested-Schleife nicht bewertet, aber ich weiß nicht, warum es nicht ausgewertet werden würde. Hier

ist die Beschreibung des Problems:

Gegeben zwei Arrays (ohne Duplikate) nums1 und nums2 wo nums1 der Elemente Teilmenge von nums2 sind. Finde alle nächsten größeren Zahlen für die Elemente von nums1 an den entsprechenden Stellen von nums2. Die nächste größere Zahl einer Zahl x in nums1 ist die erste größere Zahl rechts von nums2. Wenn es nicht existiert, gib -1 für diese Zahl aus.

Beispiel 1:

Input: nums1 = [4,1,2] nums2 = [1,3,4,2].

Ausgang: [-1,3, -1]

Erläuterung: Für Nummer 4 in der ersten Reihe, können Sie nicht die nächste größere Anzahl für sie in der zweiten Anordnung finden, so dass eine Ausgabe -1. Für Nummer 1 im ersten Array ist die nächstgrößere Nummer im zweiten Array 3. Für Nummer 2 im ersten Array gibt es keine nächste größere Zahl im zweiten Array, also Ausgabe -1.

link to original description

Und hier ist mein Code so weit:

var nums1 = [4,1,2]; 
var nums2 = [1,3,4,2]; 

    var nextGreaterElement = function(findNums, nums) { 
    var holder = []; 

    for (var i = 0; i < findNums.length; i++) { 

    //loop through the 2nd array starting at the index of the first loop's current item. 

     for (var j = nums.indexOf(findNums[i]); i < nums.length - j; i++) { 

     if (nums[j+1] > nums[j]) { 
      holder.push(nums[j+1]); 
      break; 
     } 

     if (nums[nums.length]) { 
      holder.push(-1); 
     } 
     } 
    } 
    return holder; 
}; 

nextGreaterElement(nums1, nums2) 

Vielen Dank für jede Hilfe.

Answer 1

Sie müssen das Array, das Sie suchen, sortieren, um die Suche nach der Nummer zu erleichtern. Wenn das Array groß wird, möchten Sie vielleicht einen Suchalgorithmus, um den Index im Array schneller zu finden. Mit dem Array, das sortiert betrachtet wird, können Sie die nächste Nummer als die Nummer nehmen, die um eins größer ist, und prüfen, ob Sie sich am Ende des Arrays befinden. Wenn Sie dies nicht tun, überprüfen Sie die Funktion wird Fehler, wenn Sie die Nummer nicht finden oder wenn keine Nummer größer ist. Endlich hat deine zweite if-Aussage keinen Sinn ergeben. Also überprüfe ich, ob wir uns am Ende des Arrays befinden, bevor wir -1 im Array ausgeben.

var nextGreaterElement = function(findNums, nums) { 
    var holder = []; 
    //Should sort the array to make sure you get the next largest number 
    nums = nums.sort(); 
    for (var i = 0; i < findNums.length; i++) { 

    //loop through the 2nd array starting at the index of the first loop's current item. 

     //for (var j = nums.indexOf(findNums[i]); i < nums.length - j; i++) { 
     for(var j = 0; j < nums.length; j++){ 
      //check for value in array and make sure the value is not at the end 
      if (findNums[i] == nums[j] && j != nums.length - 1) { 
      holder.push(nums[j+1]); 
      break; 
      } 
     //check for the last element in array if so output -1 
     if (j == nums.length - 1) { 
      holder.push(-1); 
     } 
     } 
    } 
    return holder; 
}; 

Answer 2

Problem: Aktualisiere Variante i, aber nicht Variante j in der inneren Schleife (j-loop)

fehlt: Debugging Effort

---

Problem Beschreibung

Theoretisch ist Ihr Code-Design s sollte jeder Wert in nums1 mit verwandten Teilen von nums2 vergleichen. Also würde es zu einer äußeren For-Schleife zu Schleife auf Nums1 und eine innere for-Schleife zu loop bezogenen Teile von nums2 für jede Iteration der äußeren for-Schleife.

In Code, Variante i ist der Index-Zeiger für findNums (d.h. nums1) während Variante j der Indexzeiger für nums ist (d nums2). Die Variante i aktualisiert sich immer sowohl in der inneren als auch in der äußeren For-Schleife, während die Variante j einmal für jede Iteration der äußeren For-Schleife gesetzt wird. Dies widerspricht dem, was Sie tun sollen.

Debugging (Ihre fehlende Arbeit)

ein Stück Papier finden und einen Stift. Setzen Sie sich hin, lassen Sie das Programm laufen und nehmen Sie die zugehörigen Informationen auf (Variante i, Variante j, findNums [i], nums [j], ...), Sie könnten herausfinden, warum Ihr Code nicht funktioniert.

---

Mögliche Lösung

var nextGreaterElement = function(findNums, nums) { 
 
    var holder = []; 
 

 
    for (var i = 0; i < findNums.length; i++) { 
 
     var hasNextGreaterElement = false; 
 
     // try to serach for next greater element 
 
     for (var j = nums.indexOf(findNums[i])+1; j < nums.length; j++) { 
 
     // handle case for next greater element is found 
 
     if (nums[j] > findNums[i]) { 
 
      holder.push(nums[j]); 
 
      hasNextGreaterElement = true; 
 
      break; 
 
     } 
 
     } 
 
     // handle case for next greater element is not found 
 
     if (!hasNextGreaterElement) { 
 
      holder.push(-1); 
 
     } 
 
    } 
 
    return holder; 
 
}; 
 

 
var findNums=[4,1,2]; 
 
var nums=[1,3,4,2]; 
 
console.log(nextGreaterElement(findNums, nums));