Постановка задачи
Предположим, что массив длины 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]].
Задав отсортированный повернутый массив num уникальных элементов, верните минимальный элемент этого массива.
Вы должны написать алгоритм, который выполняется за время 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)-го индекса.
Бинарный поиск
Поскольку массив повернут, но отсортирован, мы можем модифицировать нашу реализацию двоичного поиска. Повернутый массив имеет два сегмента, которые отсортированы. Индекс, по которому нарушается сортировка, встречается у наименьшего элемента массива.
Давайте проверим алгоритм:
- 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.
Решение на C++
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];
}
};
Решение на Golang
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.