<object id="getjk"></object>
<object id="getjk"></object>
    1. <object id="getjk"></object>
    2. <th id="getjk"></th>
      XYcooper
      • 性别: Icon_minigender_1
      • 铜雀台娱乐app下载地址

      ▯□☐Lintcode75 Find Peak Element solution 题解◘◊◘

       

      阅读更多
      □☐◘◊◘▪▫▯□☐◘◊◘▪▫▯□☐◘◊◘▪▫▯□☐◘◊◘▪▫▯□☐◘◊◘▪▫▯□☐◘◊◘▪▫▯□
      【题目描述】
      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.
      你给出一个整数数组(size为n),其具有以下特点:
      1、相邻位置的数字是不同的
      2、A[0] < A[1] 并且 A[n - 2] > A[n - 1]
      假定P是峰值的位置则满足A[P] > A[P-1]且A[P] > A[P+1],返回数组中任意一个峰值的位置。
      【注意】:数组可能包含多个峰值,只需找到其中的任何一个即可
      【题目链接】
      www.lintcode.com/en/problem/find-peak-element/
      【题目解析】
      此题可使用二分搜索。首先分析若使用传统的二分搜索,若A[mid] > A[mid - 1] && A[mid] < A[mid + 1],则找到一个peak为A[mid];若A[mid - 1] > A[mid],则A[mid]左侧必定存在一个peak,可用反证法证明:若左侧不存在peak,则A[mid]左侧元素必满足A[0] > A[1] > ... > A[mid -1] > A[mid],与已知A[0] < A[1]矛盾,证毕。同理可得若A[mid + 1] > A[mid],则A[mid]右侧必定存在一个peak。如此迭代即可得解。
      【参考答案】
      www.jiuzhang.com/solutions/find-peak-element/



      (责任编辑:XYcooper)
      分享到: