java – 算法 – 具有较小元素的最大左子数组

发布时间：2020-12-15 04:40:09 所属栏目：Java 来源：网络整理

导读：我正在开发一个程序,我需要在整数数组中获取元素的索引,这样索引右边的所有元素都大于从0到索引位置的所有元素. 例如：情况：1 – 给定输入 – {5,-2,3,8,6}然后我需要索引位置为2(即数组元素值为3)因为索引2之后的所有元素都大于从索引0开始的所有元素索引

我正在开发一个程序,我需要在整数数组中获取元素的索引,这样索引右边的所有元素都大于从0到索引位置的所有元素.

例如：

情况：1 – 给定输入 – {5,-2,3,8,6}然后我需要索引位置为2(即数组元素值为3)因为索引2之后的所有元素都大于从索引0开始的所有元素索引2即{5,3}

情况：2 – 给定输入 – {-5,6}然后我需要索引位置为2(即数值为-2的数组元素),因为索引2之后的所有元素都大于从索引0到索引2即{-5,-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,6 };
        int[] array2 = { -5,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,6]
index = 2,element = 3
[-5,6]
index = 0,element = -5

它适用于案例1但案例2失败.你能帮我解决这个问题.有没有其他更好的方法来解决这个问题,

解决方法

不幸的是,您的解决方案有几个逻辑错误.其中一个反例：[2,1,6,5](您的算法返回索引1,但答案是2).

我提出了另一种具有O(n)时间复杂度的解决方案：

>从左向右迭代计算[0..i]间隔中元素的最大值.
>从右向左迭代计算[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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!