一个数组先升序再降序，用最优时间复杂度，求最大值？例如[1,2,2,2,2,3,1]

Question

一个数组先升序再降序，求最大值？例如[1,2,2,2,2,3,1]，用最优时间复杂度，算法实现获取最大值3

Answer 1

/**
 * 使用二分查找法
 * @param arr : 先升序在降序的数组
 * @param low : 数组最小的索引
 * @param high: 数组最大的索引
 * @return    : 返回数组中的最大值
 */
public static int getMax(int[] arr, int low, int high) {
   
    while (low < high) 
    {
        int mid = low + ((high - low) >> 1);
        if (arr[mid] > arr[mid + 1]) {
            high = mid;
        } 
        else if (arr[mid] < arr[mid + 1])  {
            low = mid + 1;
        }
        else  //arr[mid]和arr[mid+1]相等的情况
        {                
            if (mid-1 >= low) //防止数组范围越界  [low~high]
            {
                if(arr[mid-1] > arr[mid])
                {
                    high = mid-1;
                }
                else if(arr[mid-1] < arr[mid])
                {
                    low = mid+1;
                }
                else //如果arr[mid-1] 和 arr[mid] 相等，即 arr[mid-1]，arr[mid],arr[mid+1]都相等，  
                    //那么就不能确定最大值在mid左边还是在mid右边，所以分别对mid左边和mid右边递归求最大
                    //值，然后比较
                {
                    int one = getMax(arr, low, mid-1);
                    int two = getMax(arr, mid+1, high);
                    
                    return one > two ? one : two;
                }
            }
            else { //如果 mid-1 < low说明  mid和low相等了。所以能够得出arr[low] == arr[high]
                return arr[low];
            }
        }
    }
    
    return arr[low];
}

Answer 2

===更新
去掉了递归、数组复制，函数返回值改为索引以方便处理空数组的情况

public class MaxFinder {
    public static void main(String[] args) {
        int[] arr = {2,3,3,3,7,13,22};
        System.out.println(arr[getMaxPos(arr)]);
    }
    
    public static int getMaxPos(int[] arr) {
        int len = arr.length;
        if(len >= 2) {
            int min = 0,
                max = len-1; // 最大值位置的索引范围闭区间
            int mid, left;
            while(max-min > 1) {
                mid = min + (max-min)/2;
                left = mid-1;
                while(left >= min) {
                    if(arr[left] > arr[mid]) {
                        max = left;
                        break;
                    }else if(arr[left] < arr[mid]) {
                        min = mid;
                        break;
                    }else {        
                        if(left == min) {
                            min = mid;
                        }
                        left--;
                    }
                }
            }
            return arr[max]>arr[min]? max : min;
        }else if(len == 1) {
            return 0;
        }else{
            return -1;
        }
    }
}

===原答案

public class Test {
    public static void main(String[] args) {
        int[] arr = {1,2,2,2,2,3,1};
        System.out.println(getMax(arr));
    }
    
    public static int getMax(int[] arr) {
        int len = arr.length;
        if(len > 2) {
            int mid = len/2,
                left = mid -1;
            while(left >= 0) {
                if(arr[left] > arr[mid]) {
                    return getMax(Arrays.copyOfRange(arr, 0, left+1));
                }else if(arr[left] < arr[mid]){
                    return getMax(Arrays.copyOfRange(arr, mid, arr.length));
                }else{
                    left--;
                }
            }
            // come here only if arr[0] to arr[mid] are all the same
            return getMax(Arrays.copyOfRange(arr, mid, arr.length));
        }else if(len == 2) {
            return arr[0] > arr[1] ? arr[0] : arr[1];
        }else{
            return arr[0];
        }
    }
}

Answer 3

可能是最短的代码:

function getMax(arr) {
        if (arr.length < 2)
            return arr[0]
        else{
            let mid = parseInt(arr.length/2)
            let flag = arr[mid-1] - arr[mid]
            if(flag > 0)
                return getMax(arr.slice(0,mid))
            else if(flag < 0)
                return getMax(arr.slice(mid))
            else {
                let a = getMax(arr.slice(0,mid))
                let b = getMax(arr.slice(mid))
                return a>b?a:b;
            }
        }
    }

性能测试(1,000,000个数,与.sort()比速度)结果如下图

测试代码如下:

    var a = [];
    var max = 1000000;
    var k = parseInt(Math.random()*max);
    for(var i = 0;i<k;i++)
        a[i] = i*2+ (Math.random()>0.5?1:-1);
    for(var i = k;i<max;i++)
        a[i] = (max-i)*2+ (Math.random()>0.5?1:-1);
    console.log(a);
    var time1 = new Date()
    console.log(getMax(a),new Date() - time1)
    var time2 = new Date()
    console.log(a.sort((x,y)=>x<y?-1:1)[a.length-1],new Date() - time2)

另外我监测了一下内存占用, 结果都是16~18MB 左右, 本来还担心因为用了slice而导致拷贝复制过多引起内存占用过大, 看来 js 的垃圾回收还不错.
性能方便是 O(lgN)

需要注意的是 js 的数组.sort()是先转 String 再进行比较,因此会出现[10,2].sort()还是[10,2]的结果,所以要添加一个比较函数.

2018-11-1更新:

参考评论的意见,增加对[2,2,2,2,2,...,2,2,3]这类长重复字符串的处理, 但实测对于随机字符串性能变化不大

function getMax(arr) {
        if (arr.length < 2)
            return arr[0]
        else{
            let right = parseInt(arr.length/2)
            let left = right - 1 
            while(right < arr.length && arr[left] == arr[right])
                right++
            if( right == arr.length || arr[left] > arr[right])
                return getMax( arr.slice(0,left+1) )
            else 
                return getMax( arr.slice(right) )
        }
    }

Answer 4

两种方案吧
第一种遍历一次，找到开始变小的那个i，a[i-1]就是最大值，复杂度O(n);
第二种，二分法，先去中间的三个值，判断这三个值是否单调，如果不是单调，中间那个就是最大值，否则根据单调方向，找到下一段数组进行二分查找。复杂度O(logn)

Answer 5

使用二分查找

===更新===
经评论区@superman369指出，忽略了重复元素的情况，由于遇到重复的元素时没有足够的信息判断应该去左半边查找还是右半边查找，只能分两趟，取最大的那个。

public class Main {
    public static void main(String[] args) {
        int[] arr = {2, 2, 2, 3, 2, 2, 2, 2, 2, 2};
        System.out.println(getMax(arr));
    }

    public static int getMax(int[] arr) {
        int left = 0;
        int right = arr.length - 1;
        // 二分查找，遇到相同元素时，向右收缩
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (arr[mid] > arr[mid + 1]) {
                right = mid;
            } else if (arr[mid] < arr[mid + 1]) {
                left = mid + 1;
            } else {
                if (arr[left] > arr[right]) {
                    right--;
                } else {
                    left++; //遇到相同元素，且无法判断方向时，向右收缩
                }
            }
        }
        int max = arr[left];

        left = 0;
        right = arr.length - 1;
        // 二分查找，遇到相同元素时，向左收缩
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (arr[mid] > arr[mid + 1]) {
                right = mid;
            } else if (arr[mid] < arr[mid + 1]) {
                left = mid + 1;
            } else {
                if (arr[left] < arr[right]) {
                    left++;
                } else {
                    right--; //遇到相同元素时，且无法判断方向时，向左收缩
                }
            }
        }
        return max > arr[left] ? max : arr[left];
    }
}

两个二分查找其实是完全一样的，只是在遇到相同元素时，一个向左收缩，一个向右收缩。但是每一部分都使用二分查找。

===原答案===

这就是个很典型的二分查找的题啊：

public class Main {
    public static void main(String[] args) {
        int[] arr = {1, 2, 2, 2, 2, 3, 1};
        System.out.println(getMax(arr));
    }

    public static int getMax(int[] arr) {
        int left = 0;
        int right = arr.length - 1;
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (arr[mid] > arr[mid + 1]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return arr[left];
    }
}

我们从右侧往左侧向最大值逼近就行了。

Answer 6

遍历
if(a[n+1]===undefined){return a[n]}
if(a[n]>a[n+1]){return a[n]}
这样？

Answer 7

你这啥条件没有啊，如果不考虑复杂度，直接 Math.max(...array) 就完事了啊

Answer 8

这个跟 Leetcode 的 33. Search in Rotated Sorted Array 异曲同工。思路是二分时判断是在前半部分还是后半部分再作跳跃。

Answer 9

遇到同样问题多谢各位大神