162. Find Peak Element

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

O texto da tarefa é traduzido do russo para o idioma selecionado. O código permanece sem alterações.

LeetCode Static

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

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

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

C# solução

correspondente/original

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++ solução

rascunho automático, revisar antes de enviar

#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 solução

correspondente/original

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 solução

correspondente/original

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 solução

correspondente/original

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 solução

correspondente/original

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

Exemplo:

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

Output: 2

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

👨‍💻

Algoritmo:

1️⃣

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

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

2️⃣

Definição направления поиска:

Сравниваем 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

vagas ativas with overlapping task tags are mostradas.

Todas as vagas

Ainda não há vagas ativas.