查找大于所有先前元素的数组元素

Question

我一直在尝试解决以下问题： 给定一个数组：1 2 2 4 4 6 5 4 5 7 8 9 11 13 找到第一个既大于所有前面的元素又小于所有后面的元素的元素。 我的想法是对数组进行排序，然后找到第一个没有改变其原始位置的元素。 你认为呢？有更好的方法吗？ 是否有一种少于O（N ^ 2）的方法来解决这个问题？ 谢谢。

- user3424107

---

糟糕..我的错，抱歉。 - Maroun

@zouZou：但他正在获取所有不移动元素的第一个元素。 - lakshman

@lakshman 如果排序的行为像我描述的那样，第一个不动的元素将是第二个7，从而得到一个无效的答案。 - Alexis C.

@MarounMaroun 为此，您需要在之前执行检查。 "将其排序，然后检查第一个不移动的位置" 的解决方案不起作用。 - Alexis C.

@Braj，发布者确实问道“有更好的方法吗？”，而您的回答在技术上并没有满足这个要求。我认为很明显，如果发帖人描述了一个O(n lg n)算法，那么O(N^2)的算法对于这个问题是行不通的。 - awksp

Answer 1

1. 从左到右扫描，跟踪当前最大值。标记任何是当前最大值的元素。
2. 从右到左扫描，跟踪当前最小值。同时跟踪当前最小值中最左边的被标记元素。

步骤1找到所有满足第一个条件的元素，步骤2同理。整个过程时间和空间复杂度都为O(n)。

- Oliver Charlesworth

Answer 2

根据@Oli的解决方案：

public static void getElement(int[] array) {
    int n = array.length;
    boolean[] maxis = new boolean[n];
    //compute max
    int max = array[0];
    maxis[0] = true;
    for (int i = 1; i < n; i++) {
        if (array[i] > max) {
            max = array[i];
            maxis[i] = true;
        }
    }
    //initialize requestedNumber, if we get -1 as a reply there is no solution
    int requestedPos = -1;
    int requestedNumber = 0;


    int min = array[n-1];
    if (maxis[n-1]) {
        requestedPos = n-1;
        requestedNumber = min;
    }

    //compute min
    //keep track of current requestedNumber
    for (int i = n - 1 ; i >= 0; i--) {
        if (array[i] < min) {
            min = array[i];
            if (maxis[i]) {
                requestedPos = i;
                requestedNumber = min;
            }
        }
    }


    System.out.println(requestedPos);
    System.out.println(requestedNumber);
}

- Kostas Kryptos

---

这很酷，但通常不是在作业问题中提供完整代码答案的好主意。 - Oliver Charlesworth

是的，几乎忘记这是一项作业，因为我们在努力证明存在一个O(n)算法。 - Kostas Kryptos

Answer 3

我认为有一种更快的方法，而不需要额外的数组或标记。

我们只需要进行一次完整的表扫描，没有其他操作，因此显然是O(n)：

public static void getFirstMinMaxElement(int[] array) {
    //compute max
    int max = array[0];
    int requestedPos = 0; //position
    int requestedNumber = max; //current
    for (int i = 1; i < array.length; i++) {
        if (array[i] > max) {
            max = array[i];
            //only assign a new requested value if there isn't any
            if (requestedPos == -1) {
                requestedPos = i;
                requestedNumber = max;
            }
        }
        //delete current requestedNumber when you find a smaller one
        //use < instead of <= if you don't care about equal elements 
        else if (array[i] <= requestedNumber) {
            requestedPos = -1;
        }
    }
    System.out.println(requestedPos); //if -1, then there is no solution
    System.out.println(requestedNumber);
}

- Kostas Kryptos