算法 - 具有較少元素的最大左側子陣列

Question

我正在研究一個程序，我需要在整數數組中獲取元素的索引，使得索引右側的所有元素都大於所有元素0到該索引位置。

例如：

Case : 1 - 給定的輸入 - { 5, -2, 3, 8, 6 }然後我需要的索引位置作爲2 (i.e array element with value 3)因爲索引2畢竟元素比開始從索引0到索引2即所有元素更大{5，-2， 3}

Case : 2 - 給定的輸入 - { -5, 3, -2, 8, 6 }然後我需要的索引位置作爲2 (i.e array element with value -2)因爲索引2畢竟元素比開始從索引0到索引2即{-5,3所有元素時，-2}

這裏是我的Java程序：

import java.util.ArrayList; 
import java.util.Arrays; 
import java.util.Collections; 
import java.util.List; 

public class ArrayProgram { 

    public static void main(String[] args) { 
     int[] array1 = { 5, -2, 3, 8, 6 }; 
     int[] array2 = { -5, 3, -2, 8, 6 }; 
     process(array1); 
     process(array2); 
    } 

    private static void process(int[] array) { 
     List<Integer> list = new ArrayList<Integer>(); 
     int maxIndex = 0; 
     list.add(array[0]); 
     System.out.println(Arrays.toString(array)); 
     for (int i = 1; i < array.length; i++) { 
      if (array[i] <= Collections.max(list)) { 
       list.add(array[i]); 
       maxIndex = i; 
      } 
     } 

     System.out.println("index = " + maxIndex + ", element = " + array[maxIndex]); 
    } 
} 

程序輸出是：

[5, -2, 3, 8, 6] 
index = 2, element = 3 
[-5, 3, -2, 8, 6] 
index = 0, element = -5 

它適用於case 1但沒有爲case 2。你能幫我解決這個問題嗎？有沒有其他更好的方法來解決這個問題，

Answer 1

不幸的是，你的解決方案有幾個邏輯錯誤。其中一個反例：[2, 1, 3, 6, 5]（您的算法返回索引1，但答案是2）。

我提出具有O(n)時間複雜度的另一解決方案：從左至右計算最大元素的[0..i]間隔

1. 迭代。
2. 從右向左迭代，計算[i+1..n]區間中元素的最小值，並將該最小值與第一步中預先計算的左邊元素的最大值進行比較。

樣品實施：

static void process(int[] array) { 
    int n = array.length; 
    if (n < 2) return; 

    int[] maxLeft = new int[n]; 
    maxLeft[0] = array[0]; 
    for (int i = 1; i < n; ++i) { 
     maxLeft[i] = Math.max(maxLeft[i-1], array[i]); 
    } 

    int minRight = array[array.length-1]; 
    for (int i = n-2; i >= 0; --i) { 
     if (maxLeft[i] < minRight) { 
      System.out.println("index = " + i + ", element = " + array[i]); 
      return; 
     } 
     minRight = Math.min(minRight, array[i]); 
    } 
}  

的Runnable：http://ideone.com/mmfvmH

Answer 2

改變了我的意見來回答。從數組末尾開始，右邊只有一個元素，左邊有n-1個元素。然後檢查最大剩餘的條件，如果滿足則該條件滿足，否則將索引移動到左側並再次檢查。

import java.util.ArrayList; 
import java.util.Arrays; 
import java.util.Collections; 
import java.util.List; 

public class ArrayProgram { 

    public static void main(String[] args) { 
     int[] array1 = { 5, -2, 3, 8, 6 }; 
     int[] array2 = { -5, 3, -2, 8, 6 }; 
     int[] array3 = { 1, 3, 5, 8, 4 }; 
     int[] array4 = { 1, 1, 1, 1, 1 }; 
     process(array1); 
     process(array2); 
     process(array3); 
     process(array4); 
    } 


    private static void process(int[] array) { 
     List<Integer> listLeft = new ArrayList<Integer>(); 
     List<Integer> listRight = new ArrayList<Integer>(); 

     //create an array that consists upto n-1 elements 
     int arraySize = array.length; 
     if (arraySize < 2){ 
      System.out.println("None"); 
      return; 
     } 
     for (int i = 0; i < arraySize - 1; i++){ 
      listLeft.add (array[i]); 
     } 
     //create an array that has the last element 
     listRight.add (array[arraySize - 1]); 

     //iterate from the last adding new elements till the condition satisfies 
     for (int i = arraySize - 2; i >= 0; i--){ 

      //if the condition is satisfied exit 
      if (Collections.max(listLeft) < Collections.min(listRight)){ 
       System.out.println("index = " + i + ", element = " + array[i]); 
       return; 
      }else{ 
       //remove an element from left and add an element to right 
       listLeft.remove (listLeft.size() - 1); 
       listRight.add (array[i]); 
      } 
     } 

     System.out.println("None"); 
    } 
} 

Answer 3

我會建議一個獲取正確輸出的算法。它將在O（n）中執行。讓我們考慮arr[]中有n元素。維護2個數組int minElementIndex[]和maxElementIndex[]。

• minElementIndex[i]存儲子陣列[（i + 1）...（n-1）]中存在的最小值元素的索引。minElementIndex[n-1]=n-1的值
• maxElementIndex[i]存儲子陣列[0 ...（i）]中存在的最大值元素的索引。 maxElementIndex[0]=0

代碼的用於填充minElementIndex [0 ... N-1]

int index=minElementIndex[n-1]; 
for(int i=n-2;i>=0;i--){ 
    minElementIndex[i] = index; 
    if(arr[i]<arr[index]) 
     index=i; 
} 

代碼用於填充maxElementIndex [0-1N的...]的值：

int index=maxElementIndex[0]; 
for(int i=1;i<n;i++){ 
    if(arr[i]>arr[index]) 
    index=i; 
    maxElementIndex[i]=index; 
} 

現在，只需按照以下方式遍歷兩個陣列：

for(int i=1;i<n-1;i++){ 
    if(arr[maxElementIndex[i]]< minElementIndex[i]){ 
     System.out.println(i); 
    } 
} 

讓我們幹運行提出的算法。

案例1：arr[5] = {5,-2,3,8,6}minElementIndex[5] = {1,2,4,4,4}和maxElementIndex[5] = {0,0,0,3,3}。顯然在i=2，arr[maxElementIndex[i]] < arr[minElementIndex[i]]這是5 < 6

案例2：arr[5] = {-5,3,-2,8,6}minElementIndex[5] = {2,2,4,4,4}和maxElementIndex[5] = {0,1,1,3,3}。很明顯在i=2,arr[maxElementIndex[i]] < arr[minElementIndex[i]]這就是3 < 6