Finden gelinde größere Element auf der rechten Seite

Question

Ich versuche, einen Algorithmus zu lösen, wobei ich das dest größer Element auf der rechten Seite eines Arrays zu finden haben reference

Für eine Instanz in der unten Array Input: [8 58, 71, 18, 31, 32, 63, 92, 43, 3, 91, 93, 25, 80, 28]

Das am wenigsten größere Element auf der rechten Seite für das erste Element 8 ist 18, z das zweite Element 58 ist 63 & so weiter. Ich brauche Hilfe bei der Logik, um den Algorithmus zu lösen. Ich beabsichtige, zuerst mit roher Gewalt mit einer Komplexität von O (n^2) zu lösen.

Der Code, den ich bis jetzt geschrieben habe, ist unter

public class Tmp { 

public static void main(String[] args) { 

    int[] arr = { 8, 58, 71, 18, 31, 32, 63, 92, 43, 3, 91, 93, 25, 80, 28 }; 
    int[] tmpArr = new int[arr.length]; 
    int pos = 0; 
    int k=0; 

    for (int i = 0; i < arr.length-1; i++) { 
     //int next = arr[i]; 
     for (int j = i + 1; j < arr.length; j++) { 
      if ((arr[j] > arr[i])) { 
      tmpArr[k]=arr[j]; // take all the values to the right of the element which are greater than it 
      k++; 
      } 
     } 

ich das zweite Array tmpArr erstellt haben alle Werte auf der rechten Seite eines Elements zu ergreifen, die als eine sie größer sind. Wahrscheinlich sortiere das Array dann & den ersten Wert nehmen. Aber diese Logik scheint mir nicht in Ordnung zu sein.

können andere Lösung

sein

for (int i = 0; i < arr.length-1; i++) { 
    int leastGreater = ? //Don't know what to initialize with 
      for (int j = i + 1; j < arr.length; j++) { 
       if ((arr[j] > arr[i])) { 
        if(arr[j]<leastGreater){ 
       leastGreater = arr[j]; 
        } 
       } 
      } 

jemand mit einer einfacheren Lösung helfen?

Answer 1

es zu lösen O(n log n) können Sie TreeSet verwenden und von rechts nach links gehen.

TreeSet<Integer> set = new TreeSet<Integer>(); 
for (int i = ar.length - 1; i >= 0; --i) { 
    set.higher(ar[i]); // what you need, may be null 
    set.add(ar[i]); 
} 

Answer 2

Der zweite Schnipsel ist fast ok:

for (int i = 0; i < arr.length; i++) { // (1) 
    int leastGreater = -1; // (2) 
    for (int j = i + 1; j < arr.length; j++) { 
     if ((arr[j] > arr[i])) { 
      if(leastGreater == -1 || arr[j]<leastGreater){ // (3) 
       leastGreater = arr[j]; 
      } 
     } 
    } 
    arr[i] = leastGrater; // (4) 
} 

1. Wir brauchen auch das letzte Element des Arrays setzen, um die Schleife laufen über das gesamte Array lassen
2. Wenn nichts den Wert gefunden wird -1, sollte so zu initialisieren, dass
3. Bedarf auch zu ersetzen, wenn nichts gefunden noch
4. stellen Sie den neuen Wert in das Array

Answer 3

Dies sollte

int a[]={8, 58, 71, 18, 31, 32, 63, 92, 43, 3, 91, 93, 25, 80, 28}; 
    int n=a.length; 
    for(int i=0;i<n-1;i++){ 
     int diff=Integer.MAX_VALUE; 
     int leastGreater=Integer.MAX_VALUE; 
     for(int j=i+1;j<n;j++){ 
      if(a[j]-a[i]>0&&diff>a[j]-a[i]){ 
       diff=a[j]-a[i]; 
       leastGreater=a[j]; 
      } 
     } 
     if(leastGreater==Integer.MAX_VALUE){ 
      System.out.println("Not Found for index "+i); 
     }else{ 
      System.out.println(leastGreater+" found for index "+i); 
     } 
    } 

arbeiten

Es prüft Differenz rechts von aktuellen Element, das> 0 d.h rechtes Element als das aktuelle sein sollte größer sein sollte.

Answer 4

Kann eine temporäre Variable verwenden, die den aktuellen/kleinsten Wert größer als das Ziel und eine Schleife angibt. Boolean ist optional, klarer. Kann auch die Temp-Variable verwenden, die als -1 -als Flag anstelle des booleschen Werts initialisiert wurde. Die Verwendung einer Schleife ist schneller für ein größeres Array und viele Anrufe. Full source

 int[] arr = { 8, 58, 71, 18, 31, 32, 63, 92, 43, 3, 91, 93, 25, 80, 28 }; 
     // Test cases 
     ap.findLeasterGreater(arr, 0); 
     ap.findLeasterGreater(arr, 1); 
     ap.findLeasterGreater(arr, 11); 
     ap.findLeasterGreater(arr, 6); 
     // without boolean 
     ap.findLeasterGreater2(arr, 0); 
     ap.findLeasterGreater2(arr, 1); 
     ap.findLeasterGreater2(arr, 11); 
     ap.findLeasterGreater2(arr, 6); 

    /* 
    * One loop L-R, check if first greater val encountered. Ini currGreater, when a new value that > orig but < currGreater, use that as 
    * the currGreater Using the location of curr greater so can return that. More useful. 
    */ 
    int findLeasterGreater(int[] arr, int loc) { 
     int nextGreaterLoc = -1; 
     boolean first = true; 
     for (int i = loc + 1; i < arr.length; i++) { 
      if (first && arr[loc] < arr[i]) { 
       first = false; 
       nextGreaterLoc = i; 
      } else if (arr[loc] < arr[i] && arr[nextGreaterLoc] > arr[i]) { 
       nextGreaterLoc = i; 
      } 
     } 
     if (nextGreaterLoc == -1) { 
      System.out.println("Not found a value bigger than " + arr[loc] + " (after location " + loc + ")"); 
     } else { 
      System.out.println("Found a value bigger :" + arr[nextGreaterLoc] + " at location " + nextGreaterLoc + " bigger than " 
        + arr[loc] + " (after location " + loc + ")"); 
     } 
     return nextGreaterLoc; 
    } 

    /* 
    * with 1 less local var - no boolean 
    */ 
    int findLeasterGreater2(int[] arr, int loc) { 
     int nextGreaterLoc = -1; 
     for (int i = loc + 1; i < arr.length; i++) { 
      if (nextGreaterLoc == -1 && arr[loc] < arr[i]) { 
       nextGreaterLoc = i; 
      } else if (nextGreaterLoc > -1 && arr[loc] < arr[i] && arr[nextGreaterLoc] > arr[i]) { 
       nextGreaterLoc = i; 
      } 
     } 
     if (nextGreaterLoc == -1) { 
      System.out.println("Not found a value bigger than " + arr[loc] + " (after location " + loc + ")"); 
     } else { 
      System.out.println("Found a value bigger :" + arr[nextGreaterLoc] + " at location " + nextGreaterLoc + " bigger than " 
        + arr[loc] + " (after location " + loc + ")"); 
     } 
     return nextGreaterLoc; 
    } 
} 

Answer 5

Dies ist sehr einfach auflösbar in O (n), müssen schauen nur, wenn die Zahl, die Sie momentan erwarten zwischen der aktuellen Lösung ist und die Anzahl mit dem Eingang entspricht, dann können Sie die Lösung aktualisieren:

public static int getNextIntToTheRight(int[] arr, int index) { 
    int ret = Integer.MAX_VALUE; // initialize 
    for (int i = index + 1; i < arr.length; i++) // for all items to the right of index 
    if (arr[i] < ret && arr[i] > arr[index]) // if the inspected item is better 
     ret = arr[i]; // update on the fly 
    return ret; // this is now the solution, if there is any, otherwise Integer.MAX_VALUE 
} 

Answer 6

Verwenden Sie binäre Suche und zwei Zeiger-Technik.zuerst das Array sortieren, gibt diese Funktion Index von mindestens größer in O(log n) falls vorhanden andernfalls kehrt -1

int LeasterGreater(int[] a, int value, int left, int right) { 
    int low = left; 
    int high = right; 
    while (low != high) { 
     int mid = (low + high)/2; 
     if (a[mid] <= value) { 
      low = mid + 1; 
     } else { 
      high = mid; 
     } 
    } 
    if (low == right) { 
     return -1; 
    } 
    return low; 
} 

Beispiel 1:

int[] arr = {8, 58, 71, 18, 31, 32, 63, 92, 43, 3, 91, 93, 25, 80, 28}; 
    Arrays.sort(arr); 
    int leastGreaterIndex = LeasterGreater(arr, 58, 0, arr.length); 
    if (leastGreaterIndex >= 0) { 
     System.out.println(arr[leastGreaterIndex]); 
    } else { 
     System.out.println("doesn't exist!"); 
    } 

output:

Beispiel 2:

int[] arr = {8, 58, 71, 18, 31, 32, 63, 92, 43, 3, 91, 93, 25, 80, 28}; 
    Arrays.sort(arr); 
    int leastGreaterIndex = LeasterGreater(arr, 93, 0, arr.length); 
    if (leastGreaterIndex >= 0) { 
     System.out.println(arr[leastGreaterIndex]); 
    } else { 
     System.out.println("doesn't exist!"); 
    } 

existiert nicht!