154. Find Minimum in Rotated Sorted Array II

leetcode hard

#array#csharp#hard#leetcode#search#sort

Task

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

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

[0,1,4,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, который может содержать дубликаты, верните минимальный элемент этого массива.

Необходимо максимально уменьшить количество операций.

Пример:

Input: nums = [1,3,5]

Output: 1

C# solution

matched/original

public class Solution {
    public int FindMin(int[] nums) {
        int low = 0, high = nums.Length - 1;
        while (low < high) {
            int pivot = low + (high - low) / 2;
            if (nums[pivot] < nums[high])
                high = pivot;
            else if (nums[pivot] > nums[high])
                low = pivot + 1;
            else
                high -= 1;
        }
        return nums[low];
    }
}

C++ solution

auto-draft, review before submit

#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) {
        int low = 0, high = nums.size() - 1;
        while (low < high) {
            int pivot = low + (high - low) / 2;
            if (nums[pivot] < nums[high])
                high = pivot;
            else if (nums[pivot] > nums[high])
                low = pivot + 1;
            else
                high -= 1;
        }
        return nums[low];
    }
}

Java solution

matched/original

class Solution {
    public int findMin(int[] nums) {
        int low = 0, high = nums.length - 1;

        while (low < high) {
            int pivot = low + (high - low) / 2;
            if (nums[pivot] < nums[high]) high = pivot;
            else if (nums[pivot] > nums[high]) low = pivot + 1;
            else high -= 1;
        }
        return nums[low];
    }
}

JavaScript solution

matched/original

var findMin = function (nums) {
    let low = 0,
        high = nums.length - 1;

    while (low < high) {
        let pivot = low + Math.floor((high - low) / 2);
        if (nums[pivot] < nums[high]) high = pivot;
        else if (nums[pivot] > nums[high]) low = pivot + 1;
        else high -= 1;
    }
    return nums[low];
};

Python solution

matched/original

class Solution:
    def findMin(self, nums: List[int]) -> int:
        low = 0
        high = len(nums) - 1
        while high > low:
            pivot = low + (high - low) // 2
            if nums[pivot] < nums[high]:
                high = pivot
            elif nums[pivot] > nums[high]:
                low = pivot + 1
            else:
                high -= 1
        return nums[low]

Go solution

matched/original

func findMin(nums []int) int {
    low, high := 0, len(nums)-1

    for low < high {
        pivot := low + (high-low)/2
        if nums[pivot] < nums[high] {
            high = pivot
        } else if nums[pivot] > nums[high] {
            low = pivot + 1
        } else {
            high -= 1
        }
    }
    return nums[low]
}

Explanation

Algorithm

1️⃣

Сравнение с правой границей:

В классическом бинарном поиске мы бы сравнивали элемент в середине (nums[mid]) с искомым значением. В нашем случае мы сравниваем его с элементом, на который указывает правый указатель (nums[high]).

2️⃣

Обновление указателей:

Если элемент в середине находится в той же половине массива, что и элемент на правой границе (nums[mid] > nums[high]), минимальный элемент должен находиться в левой половине от mid. Следовательно, сдвигаем правый указатель на позицию mid.

Если nums[mid] < nums[high], это указывает, что минимальный элемент находится в правой половине или равен mid. Сдвигаем правый указатель на mid.

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

3️⃣

Итерация до сужения диапазона поиска:

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

😎