查找数组中最大数字的有效方法

Question

这是一个面试问题有一系列整数.数组中的元素可以遵循以下模式.

1. 数字按升序排列
2. 数字按降序排列
3. 数字在开始时增加,最后减少
4. 数字在开始时减少并在最后增加

查找数组中最大数字的有效方法是什么？

Answer 1

在这种情况下,您需要做的就是确定它是否为(3).如果没有,答案是max(first,last).

在所有元素相等的情况下,您需要彻底搜索数组以显示中间某处没有一个高数字.所以我认为确定你是否在(3)中是O(n).

Answer 2

那么,你有个案

1. 最后一个号码.
2. 第一个数字.
3. 从头到尾移动,在第一次下降时停止并打印前一个数字.
4. 比较第一个和最后一个数字

如果您不知道自己处于哪种情况,那么您可以通过执行以下操作来查找最大值(在C类伪代码中):

for (int i=0; i<end; ++i) {
    if (array[i] < array[i+1]) {
        // CASE 1 or 3
        for (int j=i+1; j<end; ++j) {
            if (array[j] > array[j+1]) {
                // CASE 3
                return array[j];
            }
         }
         // CASE 1
         return array[end];
     }
}
// CASE 2 or 4
return max(array[0],array[end]);