leetcode Binary Search

leetcode 162题

Posted by franki on January 9, 2021

leetcode 162题 寻找峰值

峰值元素是指其值大于左右相邻值的元素。

给定一个输入数组 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。

数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞。

示例1:

输入: nums = [1,2,3,1]
输出: 2
解释: 3 是峰值元素，你的函数应该返回其索引 2。 

示例2:

输入: nums = [1,2,1,3,5,6,4]
输出: 1 或 5
解释: 你的函数可以返回索引 1，其峰值元素为 2；
或者返回索引 5， 其峰值元素为 6。

思路

1 顺序查找法

2 二分查找法

代码

// 顺序查找
var findPeakElement = function(nums) {
    const len = nums.length;
    let i;
    for (i=0; i<len-1; i++) {
        if (nums[i] > nums[i+1]) {
            return i;
        }
    }
    return i;
};

// 二分法
var findPeakElement = function(nums) {
  let l = 0, r = nums.length - 1;
  while (l < r) {
    const mid = Math.floor((r - l) / 2) + l;
    if (nums[mid] > nums[mid + 1]) {
      r = mid;
   } else {
     l = mid + 1;
   }
  }
  return l;
}

复杂度分析

  • 时间复杂度: O(N) / O(logN)
  • 空间复杂度: O(1)
CATALOG
    FEATURED TAGS
    前端开发 H5 JavaScript 设计模式 browser jQuery 源码分析 生活 leetcode Array Stack Queue Linked List 剑指offer Binary Search Tree Binary Tree Breadth-First Search Depth-First Search String Set Binary Search Sliding Window Backtracking Dynamic Programming Two Pointers Union Find Sort Bit Operation Recursion Map Graph Search Hash LinkedList 复盘 QuickSort Trie Design MinHeap Traverse Min Heap Node.js BackEnd SQL MySQL Design Patterns Network 计算机网络 Python SVG
    FRIENDS