die größtmögliche Differenz in einem Array mit dem kleineren ganzzahligen früher auftretenden

Question

Dies ist ein Interview Frage:

Finden Sie die größtmögliche Differenz in einem Array von ganzen Zahlen, so dass die kleinere ganze Zahl früher in der Matrix auftritt.

Einschränkung: Zahlen sind nicht eindeutig. Der Bereich ist Integer-Bereich von Java. (Oder eine andere Sprache)

Beispiel:

Eingang 1: {1, 100, 2, 105, -10, 30, 100}

Der größte Unterschied zwischen -10 und 100 -> 110 (hier -10 beim 5. Index und 100 ist an den 7. index)

Eingang 2: {1, 100, 2, 105, -10, 30, 80}

der größte Unterschied zwischen 1 und 105 -> 104 (hier ist 1 am 1. Index und 105 am 4. Index)

Mögliche Lösung:

Ein Ansatz ist für alle möglichen Unterschiede zu überprüfen und verfolgen Sie den größten Unterschied bis jetzt O (n^2) Komplexität.

kann dies in besser als O (n^2) Zeit getan werden?

Answer 1

Start aus dem letzten Elemente und rückwärts bewegen. behalte das größte bisher aufgetretene Element im Gedächtnis. für jedes Element von der Max subtrahieren und an der jeweiligen Position speichern.

Sie können auch ein Element behalten, um die maximale Differenz zu speichern und die Ausgabe sofort zu geben. O (n) Zeit, O (1) Raum.

int max = INT_MIN; 
int maxdiff = 0; 

for (i = sizeof(arr)/sizeof(int) - 1; i >= 0; i--) { 
    if (max < arr[i]) { 
    max = arr[i]; 
    } 
    int diff = max - arr[i]; 
    if (maxdiff < diff) { 
    maxdiff = diff; 
    } 
} 

print maxdiff; 

Answer 2

Ich bin mir ziemlich sicher, dass dies Ihr Problem lösen soll:

int largestNumber = Integer.MIN_VALUE; 
    int smallestNumber = Integer.MAX_VALUE; 

    for(int i = 0; i < yourArray.Length; i++) 
    { 
     if(yourArray[i] > largestNumber) 
      largestNumber = yourArray[i]; 

     if(yourArray[i] < smallestNumber) 
      smallestNumber = yourArray[i]; 

    } 

    int biggestDifference = largestNumber - smallestNumber ; 

Answer 3

Ich schlage vor, dass der größte Unterschied ist, immer zwischen der größten Anzahl und der kleinsten Zahl davor oder zwischen der kleinsten Zahl und der größten Zahl danach. Diese können in linearer Zeit bestimmt werden.

Answer 4

Dhandeeps Algorithmus ist gut und Viveks Übersetzung des Codes in Java funktioniert! Außerdem können wir auch das Array scannen normal und nicht in umgekehrter Richtung:

int seed[] = {1, 100, 2, 105, -10, 30, 100}; 
int maxDiff=Integer.MIN_VALUE, minNumber = Integer.MAX_VALUE; 

for (int i = 0; i < seed.length ; i++){ 
    if(minNumber > seed[i]) 
     minNumber = seed[i]; 

    maxDiff = Math.max(maxDiff, (seed[i]-minNumber)); 
} 
System.out.println(maxDiff); 

Answer 5

Dank @Dhandeep Jain für die Antwort. Es ist die Java-Version:

//int seed[] = {1, 100, 2, 105, -10, 30, 100}; 
     int seed[] = {1, 100, 2, 105, -10, 30, 80}; 
     int maxDiff=Integer.MIN_VALUE, maxNumber = Integer.MIN_VALUE; 

     for (int i = (seed.length-1); i >=0 ; i--){ 
      if(maxNumber < seed[i]) 
       maxNumber = seed[i]; 

      maxDiff = Math.max(maxDiff, (maxNumber - seed[i])); 
     } 
     System.out.println(maxDiff); 

Answer 6

public class Test{ 

    public static void main(String[] args){ 

     int arr1[] = {1,2,5,7,9}; 
     int arr2[] = {20,25,26,35}; 
     int diff = 0; 
     int max = 0; 

     for(int i=0;i<arr1.length;i++){ 
      for(int j=0;j<arr2.length;j++){ 

       diff = Math.abs(arr1[i]-arr2[j]); 
       if(diff > max){ 
        max = diff; 
       } 
      } 
     } 
    System.out.println(max); 
    } 
} 

Answer 7

// Solution Complexity : O(n) 
    int maxDiff(int a[], int n){ 
     // Find difference of adjacent elements 
     int diff[n+1]; 
     for (int i=0; i < n-1; i++) 
      diff[i] = a[i+1] - a[i]; 

     // Now find the maximum sum sub array in diff array 
     int max_diff = diff[0]; 
     for (int i = 1 ; i < n-1 ; i++) { 
      if(diff[i-1] > 0) diff[i] += diff[i-1]; 
      if(max_diff < diff[i]) max_diff = diff[i]; 
     } 
     return max_diff; 
    } 

Answer 8

zuerst die Differenz zwischen den benachbarten Elementen des Arrays finden und speichern, alle Unterschiede in einer Hilfsgruppe diff [] die Größe n-1. Jetzt werden diese Probleme zum Finden des maximalen Summen-Subarrays dieses Differenz-Arrays.

Answer 9

public static void findDifference(Integer arr[]) { 
    int indexStart = 0; 
    int indexMin = 0; 
    int indexEnd = 1; 
    int min = arr[0]; 
    int diff = arr[1] - arr[0]; 
    for (int counter = 1; counter < arr.length; counter++) { 
     if (arr[counter] - min > diff) { 
      diff = arr[counter] - min; 
      indexEnd = counter; 
      indexStart = indexMin; 
     } 
     if (arr[counter] < min) { 
      min = arr[counter]; 
      indexMin = counter; 
     } 
    } 
    System.out.println("indexStart = " + indexStart); 
    System.out.println("indexEnd = " + indexEnd); 
    System.out.println("diff = " + diff); 
} 

Answer 10

Ruby-Lösung:

a = [3, 6, 8, 1, 5] 
min = 10**6 
max_diff = -10**6 
a.each do |x| 
    min = x if x < min 
    diff = x - min 
    max_diff = diff if diff > max_diff 
end 
puts max_diff