162. Find Peak Element

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

선택한 UI 언어에 맞게 문제 텍스트를 러시아어에서 번역합니다. 코드는 변경하지 않습니다.

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 표시됨.

전체 채용

아직 활성 채용이 없습니다.