153. Find Minimum in Rotated Sorted Array

LeetCode medium оригинал: C# #array #csharp #leetcode #medium #search #sort #two-pointers

LeetCode Static

Предположим, что массив длиной n, отсортированный в порядке возрастания, повернут от 1 до n раз. Например, массив nums = [0,1,2,4,5,6,7] может стать:

[4,5,6,7,0,1,2], если он был повернут 4 раза.

[0,1,2,4,5,6,7], если он был повернут 7 раз.

Обратите внимание, что поворот массива [a[0], a[1], a[2], ..., a[n-1]] 1 раз приводит к массиву [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Для данного отсортированного и повернутого массива nums с уникальными элементами верните минимальный элемент этого массива.

C# решение

сопоставлено/оригинал

public class Solution {
    public int FindMin(int[] nums) {
        if (nums.Length == 1) {
            return nums[0];
        }
        int left = 0, right = nums.Length - 1;
        if (nums[right] > nums[0]) {
            return nums[0];
        }
        while (right >= left) {
          
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[mid + 1]) {
                return nums[mid + 1];
            }
            if (nums[mid - 1] > nums[mid]) {
                return nums[mid];
            }
            if (nums[mid] > nums[0]) {
                left = mid + 1;
            } else {
                               right = mid - 1;
            }
        }
        return Int32.MaxValue;
    }
}

C++ решение

auto-draft, проверить перед отправкой

#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 FindMin(vector<int>& nums) {
        if (nums.size() == 1) {
            return nums[0];
        }
        int left = 0, right = nums.size() - 1;
        if (nums[right] > nums[0]) {
            return nums[0];
        }
        while (right >= left) {
          
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[mid + 1]) {
                return nums[mid + 1];
            }
            if (nums[mid - 1] > nums[mid]) {
                return nums[mid];
            }
            if (nums[mid] > nums[0]) {
                left = mid + 1;
            } else {
                               right = mid - 1;
            }
        }
        return Int32.MaxValue;
    }
}

Java решение

сопоставлено/оригинал

class Solution {
    public int findMin(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        int left = 0, right = nums.length - 1;
        if (nums[right] > nums[0]) {
            return nums[0];
        }

        while (right >= left) {
           
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[mid + 1]) {
                return nums[mid + 1];
            }
            if (nums[mid - 1] > nums[mid]) {
                return nums[mid];
            }
            if (nums[mid] > nums[0]) {
                left = mid + 1;
            } else {
            }
        }
        return Integer.MAX_VALUE;
    }
}

JavaScript решение

сопоставлено/оригинал

var findMin = function (nums) {
    if (nums.length == 1) {
        return nums[0];
    }
    if (nums[right] > nums[0]) {
        return nums[0];
    }
    while (right >= left) {
        let mid = left + Math.floor((right - left) / 2);
        if (nums[mid] > nums[mid + 1]) {
            return nums[mid + 1];
        }
        if (nums[mid - 1] > nums[mid]) {
            return nums[mid];
        }
        if (nums[mid] > nums[0]) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return Number.MAX_VALUE;
};

Python решение

сопоставлено/оригинал

class Solution:
    def findMin(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]

        left = 0

        right = len(nums) - 1

        if nums[right] > nums[0]:
            return nums[0]
        while right >= left:
            
            mid = left + (right - left) // 2
            if nums[mid] > nums[mid + 1]:
                return nums[mid + 1]
            if nums[mid - 1] > nums[mid]:
                return nums[mid]
            if nums[mid] > nums[0]:
                left = mid + 1
            else:
                right = mid - 1

Go решение

сопоставлено/оригинал

func findMin(nums []int) int {
    if len(nums) == 1 {
        return nums[0]
    }
    left := 0
    right := len(nums) - 1

    if nums[right] > nums[0] {
        return nums[0]
    }

    for right >= left {

        mid := left + (right-left)/2
        if nums[mid] > nums[mid+1] {
            return nums[mid+1]
        }
        if mid > 0 && nums[mid-1] > nums[mid] {
            return nums[mid]
        }
        if nums[mid] > nums[0] {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }

    return -1
}

Algorithm

Пример:

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

Output: 1

Explanation: The original array was [1,2,3,4,5] rotated 3 times.

👨‍💻

Алгоритм:

1️⃣

Нахождение середины массива:

Определите элемент, находящийся посередине массива.

2️⃣

Определение направления поиска:

Если элемент в середине больше первого элемента массива, это означает, что точка перегиба (минимальный элемент) находится справа от середины.

Если элемент в середине меньше первого элемента массива, это указывает на то, что точка перегиба находится слева от середины.

3️⃣

Остановка поиска при нахождении точки перегиба:

Поиск прекращается, когда найдена точка перегиба, когда выполняется одно из двух условий:

nums[mid] > nums[mid + 1] – следовательно, mid+1 является наименьшим элементом.

nums[mid - 1] > nums[mid] – следовательно, mid является наименьшим элементом.

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.