资讯专栏INFORMATION COLUMN

9 .leetcode Peak Index in a Mountain Array

txgcwm / 1491人阅读

摘要:题目例子我的解法其他解法求最大值然后求二分法查找

1 题目

Let"s call an array A a mountain if the following properties hold:

A.length >= 3
There exists some 0 < i < A.length - 1 such that A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1]
Given an array that is definitely a mountain, return any i such that A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1].

例子
Input: [0,1,0]
Output: 1
Input: [0,2,1,0]
Output: 1
我的解法
var peakIndexInMountainArray = function(A) {
     let i = 0
     while (i < A.length){
         if (A[i] > A[i+1]){
             break
            }
         i++
     }
    return i
};
Runtime: 60 ms, faster than 85.20% of JavaScript online submissions for Peak Index in a Mountain Array.
Memory Usage: 35 MB, less than 52.70% of JavaScript online submissions for Peak Index in a Mountain Array.
其他解法
var peakIndexInMountainArray = function(A) {
    return A.indexOf(Math.max(...A));
};

求最大值然后求index

var peakIndexInMountainArray = function(A) {
  function mid(a,b) {
    return Math.floor((b-a)/2);
  } 

  let left = 0, right = A.length-1; 
  let pivot = mid(left, right);

  while ( A[pivot-1]>A[pivot] || A[pivot]A[pivot+1]) {
      right = pivot;
      pivot = mid(left, right)
    } else {
      left = pivot;
      pivot += mid(left, right)
    }
  }

  return pivot;
};

二分法查找

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/103537.html

相关文章

  • Leetcode PHP题解--D12 852. Peak Index in a Mountain

    摘要:题目链接题目分析这个题目比较简单。要求返回数组中最大值的索引。思路先用找到最大值,再用获取最大值的索引。最终代码若觉得本文章对你有用,欢迎用爱发电资助。 852. Peak Index in a Mountain Array 题目链接 852. Peak Index in a Mountain Array 题目分析 这个题目比较简单。要求返回数组中最大值的索引。 思路 先用max找到最...

    luffyZh 评论0 收藏0
  • [LeetCode] 852. Peak Index in a Mountain Array

    Problem Lets call an array A a mountain if the following properties hold: A.length >= 3There exists some 0 < i < A.length - 1 such that A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1]...

    ispring 评论0 收藏0
  • [Lintcode] Find Peak Element 找峰值

    摘要:找出该矩阵的一个峰值元素,返回他的坐标原题链接一维二分搜索复杂度时间空间思路最直观的方法是遍历整个矩阵,但这要的时间。 Find Peak Element I A peak element is an element that is greater than its neighbors. Given an input array where num[i] ≠ num[i+1], fi...

    leiyi 评论0 收藏0
  • [Leetcode] Find Minimum in Rotated Sorted Array 找旋

    摘要:二分迭代法复杂度时间空间递归栈空间思路找旋转数组的起点,实际上类似找一个山谷,只要两边都比中间高就对了,这和这题很像。 Find Minimum in Rotated Sorted Array I Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 ...

    notebin 评论0 收藏0
  • [LeetCode] 702. Search in a Sorted Array of Unknow

    Problem Given an integer array sorted in ascending order, write a function to search target in nums. If target exists, then return its index, otherwise return -1. However, the array size is unknown t...

    zlyBear 评论0 收藏0

发表评论

0条评论

txgcwm

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<