LeetCode — Найти минимум в отсортированном с поворотом массиве

Постановка задачи

Предположим, что массив длины 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] , а[0], а[1], а[2], …, а[п — 2]].

Учитывая отсортированный повернутый массив nums из уникальных элементов, вернуть минимальный элемент этого массива.

Вы должны написать алгоритм, который работает за время O(log n).

Постановка задачи взята с: https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/.

Пример 1:

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

Пример 2:

Input: nums = [4, 5, 6, 7, 0, 1, 2]
Output: 0
Explanation: The original array was [0, 1, 2, 4, 5, 6, 7] and it was rotated 4 times.

Пример 3:

Input: nums = [11, 13, 15, 17]
Output: 11
Explanation: The original array was [11, 13, 15, 17] and it was rotated 4 times.

Ограничения:

- n == nums.length
- 1 <= n <= 5000
- -5000 <= nums[i] <= 5000
- All the integers of nums are unique
- nums is sorted and rotated between 1 and n times

Объяснение

Подход грубой силы

Наивный подход состоит в том, чтобы выполнять линейный поиск, который занимает O(N) время. Нам нужно найти i индекс, в котором меньшее число стоит после (i — 1)th индекса.

Бинарный поиск

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

Проверим алгоритм:

- set low = 0
      high = nums.size() - 1

- loop while low < high
  - set mid = low + (high - low) / 2

  - if nums[low] <= nums[mid] && nums[high] >= nums[mid]
    - set high = mid - 1
  - else if nums[low] <= nums[mid] && nums[high] <= nums[mid]
    - set low = mid + 1
  - else if nums[mid] <= nums[low]
    - set high = mid

- return nums[low]

Давайте проверим наши решения на C++, Golang и Javascript.

С++ решение

class Solution {
public:
    int findMin(vector<int>& nums) {
        int low = 0;
        int high = nums.size() - 1;

        while(low < high) {
            int mid = low + (high - low) / 2;

            if(nums[low] <= nums[mid] && nums[high] >= nums[mid])
                high = mid - 1;
            else if(nums[low] <= nums[mid] && nums[high] <= nums[mid])
                low = mid + 1;
            else if(nums[mid] <= nums[low])
                high = mid;
        }

        return nums[low];
    }
};

Голанг решение

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

    for low < high {
        mid = low + (high - low) / 2

        if nums[low] <= nums[mid] && nums[high] >= nums[mid] {
            high = mid - 1
        } else if nums[low] <= nums[mid] && nums[high] <= nums[mid] {
            low = mid + 1
        } else if nums[mid] <= nums[low] {
            high = mid
        }
    }

    return nums[low]
}

Javascript-решение

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

    while(low < high) {
        let mid = low + Math.floor((high - low) / 2);

        if(nums[low] <= nums[mid] && nums[high] >= nums[mid])
            high = mid - 1;
        else if(nums[low] <= nums[mid] && nums[high] <= nums[mid])
            low = mid + 1;
        else if(nums[mid] <= nums[low])
            high = mid;
    }

    return nums[low];
};

Давайте запустим наш алгоритм.

Input: nums = [4, 5, 6, 7, 0, 1, 2]

Step 1: low = 0
        high = nums.size() - 1
             = 7 - 1
             = 6

Step 2: loop while low < high
          0 < 6
          true

          mid = low + (high - low) / 2
              = 0 + (6 - 0) / 2
              = 3

          if nums[low] <= nums[mid] && nums[high] >= nums[mid]
             nums[0] <= nums[3] && nums[6] >= nums[3]
             4 <= 7 && 2 >= 7
             false

          else if nums[low] <= nums[mid] && nums[high] >= nums[mid]
                  nums[0] <= nums[3] && nums[6] <= nums[3]
                  4 <= 7 && 2 <= 7
                  true

                  low = mid + 1
                      = 3 + 1
                      = 4

Step 3: loop while low < high
          4 < 6
          true

          mid = low + (high - low) / 2
              = 4 + (6 - 4) / 2
              = 4 + 1
              = 5

          if nums[low] <= nums[mid] && nums[high] >= nums[mid]
             nums[4] <= nums[5] && nums[6] >= nums[5]
             0 <= 1 && 2 >= 1
             true

             high = mid - 1
                  = 5 - 1
                  = 4

Step 4: loop while low < high
          4 < 4
          false

Step 5: return nums[low]
               nums[4]
               0

We return the answer as 0.

Первоначально опубликовано на https://alkeshghorpade.me.