LintCode 75. Find Peak Element 原创Java参考解答

LintCode 75. Find Peak Element 原创Java参考解答

问题描述

http://www.lintcode.com/en/problem/find-peak-element/

There is an integer array which has the following features:

  • The numbers in adjacent positions are different.
  • A[0] < A[1] && A[A.length – 2] > A[A.length – 1].

We define a position P is a peek if:

A[P] > A[P-1] && A[P] > A[P+1]

Find a peak element in this array. Return the index of the peak.

Notice

The array may contains multiple peeks, find any of them.

Example

Given [1, 2, 1, 3, 4, 5, 7, 6]

Return index 1 (which is number 2) or 6 (which is number 7)

解题思路

题目是求一个数值大于相邻位置两数的峰值数位置。

题目最关键条件:第一个数和第二数是上升关系A[0] < A[1],倒数第二个数和倒数第一个数是下降关系A[A.length - 2] > A[A.length - 1]。这个条件说明了,整个数列的变化,是先上升,后下降。那说明在整个区间中,总有一个从上升到下降的拐点,即一定会存在一个峰值。

最简单地解法就是遍历数组,只要找到一个大于两边的元素就可以了,但复杂度为O(N)。这题可以用复杂度更优化O(logN)的二分法来做。

用二分法不断缩减搜索范围找峰值。因为题目只求一个峰值,那么二分法始终会找到一个峰值。

  • 如果二分法找到中间位置的数A[mid]大于相邻两位置的数,则A[mid]即为峰值。
  • 如果 A[mid] < A[mid+1],说明mid到end这段区间是一个先上升,后下降的区间,一定存在有峰值(并不是说左边就一定没有,只是说右边一定有,所以往右边走)
  • 同理,A[mid] < A[mid – 1]的话,说明 start 到 mid这段区间也是先上升,后下降的区间。也能确定左边一定有峰值。

 

参考代码

class Solution { 
    /** 
     * @param A: An integers array. 
     * @return: return any of peek positions. 
     */ 
    public int findPeak(int[] A) { 
        if (A == null || A.length == 0) { 
            return -1; 
        } 
         
        int start = 0; 
        int end = A.length - 1; 
         
        while (start + 1 < end) { 
            int mid = start + (end - start) / 2; 
            if (A[mid] > A[mid - 1] && A[mid] > A[mid + 1]) { 
                return mid; 
            } else if (A[mid] < A[mid - 1]) { 
                end = mid; 
            } else { 
                start = mid; 
            } 
        } 
         
        if (A[start] > A[end]) { 
            return start; 
        } else { 
            return end; 
        } 
    } 
} 


相关题目

LintCode All in One 原创题目讲解汇总

发表回复

您的电子邮箱地址不会被公开。