162. Find Peak Element

LeetCode medium original: C# #array #csharp #leetcode #medium #search

题目文本会按所选界面语言从俄语翻译；代码保持不变。

LeetCode Static

Пиковым elementом называется element, который строго больше своих соседей.

Для 数组а целых чисел nums с индексацией с нуля find пиковый element и return его индекс. Если в 数组е несколько пиков, return индекс любого из пиков.

Вы можете представить, что nums[-1] = nums[n] = -∞. Другими словами, element всегда считается строго большим, чем сосед, находящийся за пределами 数组а.

C# 解法

匹配/原始

public class Solution {
    public int FindPeakElement(int[] nums) {
        return Search(nums, 0, nums.Length - 1);
    }
    public int Search(int[] nums, int l, int r) {
        if (l == r)
            return l;
        int mid = (l + r) / 2;
        if (nums[mid] > nums[mid + 1])
            return Search(nums, l, mid);
        return Search(nums, mid + 1, r);
    }
}

C++ 解法

自动草稿，提交前请检查

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int FindPeakElement(vector<int>& nums) {
        return Search(nums, 0, nums.size() - 1);
    }
    public int Search(vector<int>& nums, int l, int r) {
        if (l == r)
            return l;
        int mid = (l + r) / 2;
        if (nums[mid] > nums[mid + 1])
            return Search(nums, l, mid);
        return Search(nums, mid + 1, r);
    }
}

Java 解法

匹配/原始

public class Solution {
    public int findPeakElement(int[] nums) {
        return search(nums, 0, nums.length - 1);
    }

    public int search(int[] nums, int l, int r) {
        if (l == r) return l;
        int mid = (l + r) / 2;
        if (nums[mid] > nums[mid + 1]) return search(nums, l, mid);
        return search(nums, mid + 1, r);
    }
}

JavaScript 解法

匹配/原始

var findPeakElement = function (nums) {
    return search(nums, 0, nums.length - 1);
};

var search = function (nums, l, r) {
    if (l == r) return l;
    let mid = Math.floor((l + r) / 2);
    if (nums[mid] > nums[mid + 1]) return search(nums, l, mid);
    return search(nums, mid + 1, r);
};

Python 解法

匹配/原始

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        return self.search(nums, 0, len(nums) - 1)

    def search(self, nums: List[int], l: int, r: int) -> int:
        if l == r:
            return l
        mid = (l + r) // 2
        if nums[mid] > nums[mid + 1]:
            return self.search(nums, l, mid)
        return self.search(nums, mid + 1, r)

Go 解法

匹配/原始

func findPeakElement(nums []int) int {
    return search(nums, 0, len(nums)-1)
}

func search(nums []int, l int, r int) int {
    if l == r {
        return l
    }
    mid := (l + r) / 2
    if nums[mid] > nums[mid+1] {
        return search(nums, l, mid)
    }
    return search(nums, mid+1, r)
}

Algorithm

示例:

Input: nums = [1,2,3,1]

Output: 2

Explanation: 3 is a peak element and your function should return the index number 2.

👨‍💻

算法:

1️⃣

Начальная проверка:

Определяем средний element 数组а mid как mid = low + (high - low) / 2. Это помогает предотвратить возможное переполнение при больших значениях индексов.

2️⃣

定义 направления поиска:

Сравниваем element nums[mid] с его правым соседом nums[mid + 1]. Если nums[mid] меньше nums[mid + 1], это указывает на наличие восходящей последовательности, и мы двигаемся вправо, устанавливая low = mid + 1. Это потому, что пик гарантированно находится в правой части.

Если nums[mid] больше nums[mid + 1], это указывает на наличие нисходящей последовательности, и пик находится либо в mid, либо слева от него, тогда устанавливаем high = mid.

3️⃣

Завершение поиска:

Процесс продолжается до тех пор, пока low не станет равным high, что означает сужение поисковой области до одного elementа, который и является пиком, поскольку мы исключили все другие возможности.

😎

Vacancies for this task

活跃职位 with overlapping task tags are 已显示.

所有职位

目前还没有活跃职位。