同步操作将从 doocs/leetcode 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。
给你一个可能存在 重复 元素值的数组 numbers
,它原来是一个升序排列的数组,并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如,数组 [3,4,5,1,2]
为 [1,2,3,4,5]
的一次旋转,该数组的最小值为1。
示例 1:
输入:[3,4,5,1,2] 输出:1
示例 2:
输入:[2,2,2,0,1] 输出:0
注意:本题与主站 154 题相同:https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array-ii/
方法一:二分查找
二分查找的变种,需要考虑重复元素的情况。
我们定义两个指针 $l$ 和 $r$ 分别指向数组的左右两端,每次取中间元素 numbers[mid]
与右端元素 numbers[r]
比较,有以下三种情况:
numbers[mid] > numbers[r]
:中间元素一定不是最小值,因此 $l = mid + 1$;numbers[mid] < numbers[r]
:中间元素可能是最小值,因此 $r = mid$;numbers[mid] == numbers[r]
:中间元素一定不是最小值,因此 $r = r - 1$。循环结束时,指针 $l$ 和 $r$ 指向同一个元素,即为最小值。
时间复杂度 $(\log n)$,空间复杂度 $O(1)$。其中 $n$ 为数组长度。
注意,我们也可以每次取中间元素 numbers[mid]
与左端元素 numbers[l]
比较,但需要考虑当前 $[l,..r]$ 区间内的元素是否已经有序,即是否满足 numbers[l] < numbers[r]
,如果满足,直接返回 numbers[l]
即可。其它情况与上述方法类似。
class Solution:
def minArray(self, numbers: List[int]) -> int:
l, r = 0, len(numbers) - 1
while l < r:
m = (l + r) >> 1
if numbers[m] > numbers[r]:
l = m + 1
elif numbers[m] < numbers[r]:
r = m
else:
r -= 1
return numbers[l]
class Solution:
def minArray(self, numbers: List[int]) -> int:
l, r = 0, len(numbers) - 1
while l < r:
if numbers[l] < numbers[r]:
return numbers[l]
mid = (l + r) >> 1
if numbers[mid] > numbers[l]:
l = mid + 1
elif numbers[mid] < numbers[l]:
r = mid
else:
l += 1
return numbers[l]
class Solution {
public int minArray(int[] numbers) {
int l = 0, r = numbers.length - 1;
while (l < r) {
int m = (l + r) >>> 1;
if (numbers[m] > numbers[r]) {
l = m + 1;
} else if (numbers[m] < numbers[r]) {
r = m;
} else {
--r;
}
}
return numbers[l];
}
}
class Solution {
public int minArray(int[] numbers) {
int l = 0, r = numbers.length - 1;
while (l < r) {
if (numbers[l] < numbers[r]) {
break;
}
int m = (l + r) >>> 1;
if (numbers[m] > numbers[l]) {
l = m + 1;
} else if (numbers[m] < numbers[l]) {
r = m;
} else {
++l;
}
}
return numbers[l];
}
}
class Solution {
public:
int minArray(vector<int>& numbers) {
int l = 0, r = numbers.size() - 1;
while (l < r) {
int mid = (l + r) >> 1;
if (numbers[mid] > numbers[r]) {
l = mid + 1;
} else if (numbers[mid] < numbers[r]) {
r = mid;
} else {
--r;
}
}
return numbers[l];
}
};
class Solution {
public:
int minArray(vector<int>& numbers) {
int l = 0, r = numbers.size() - 1;
while (l < r) {
if (numbers[l] < numbers[r]) {
break;
}
int mid = (l + r) >> 1;
if (numbers[mid] > numbers[l]) {
l = mid + 1;
} else if (numbers[mid] < numbers[l]) {
r = mid;
} else {
++l;
}
}
return numbers[l];
}
};
func minArray(numbers []int) int {
l, r := 0, len(numbers)-1
for l < r {
mid := (l + r) >> 1
if numbers[mid] > numbers[r] {
l = mid + 1
} else if numbers[mid] < numbers[r] {
r = mid
} else {
r--
}
}
return numbers[l]
}
func minArray(numbers []int) int {
l, r := 0, len(numbers)-1
for l < r {
if numbers[l] < numbers[r] {
break
}
mid := (l + r) >> 1
if numbers[mid] > numbers[l] {
l = mid + 1
} else if numbers[mid] < numbers[l] {
r = mid
} else {
l++
}
}
return numbers[l]
}
/**
* @param {number[]} numbers
* @return {number}
*/
var minArray = function (numbers) {
let l = 0,
r = numbers.length - 1;
while (l < r) {
let m = (l + r) >>> 1;
if (numbers[m] > numbers[r]) {
l = m + 1;
} else if (numbers[m] < numbers[r]) {
r = m;
} else {
--r;
}
}
return numbers[l];
};
/**
* @param {number[]} numbers
* @return {number}
*/
var minArray = function (numbers) {
let l = 0,
r = numbers.length - 1;
while (l < r) {
if (numbers[l] < numbers[r]) {
break;
}
let m = (l + r) >>> 1;
if (numbers[m] > numbers[l]) {
l = m + 1;
} else if (numbers[m] < numbers[l]) {
r = m;
} else {
++l;
}
}
return numbers[l];
};
impl Solution {
pub fn min_array(numbers: Vec<i32>) -> i32 {
let mut l = 0;
let mut r = numbers.len() - 1;
while l < r {
let mid = l + r >> 1;
match numbers[mid].cmp(&numbers[r]) {
std::cmp::Ordering::Less => r = mid,
std::cmp::Ordering::Equal => r -= 1,
std::cmp::Ordering::Greater => l = mid + 1,
}
}
numbers[l]
}
}
impl Solution {
pub fn min_array(numbers: Vec<i32>) -> i32 {
let mut l = 0;
let mut r = numbers.len() - 1;
while l < r {
if numbers[l] < numbers[r] {
break;
}
let mid = l + r >> 1;
match numbers[mid].cmp(&numbers[l]) {
std::cmp::Ordering::Less => r = mid,
std::cmp::Ordering::Equal => l += 1,
std::cmp::Ordering::Greater => l = mid + 1,
}
}
numbers[l]
}
}
public class Solution {
public int MinArray(int[] numbers) {
int l = 0, r = numbers.Length - 1;
while (l < r) {
int m = (l + r) >> 1;
if (numbers[m] > numbers[r]) {
l = m + 1;
} else if (numbers[m] < numbers[r]) {
r = m;
} else {
--r;
}
}
return numbers[l];
}
}
public class Solution {
public int MinArray(int[] numbers) {
int l = 0, r = numbers.Length - 1;
while (l < r) {
if (numbers[l] < numbers[r]) {
break;
}
int m = (l + r) >> 1;
if (numbers[m] > numbers[l]) {
l = m + 1;
} else if (numbers[m] < numbers[l]) {
r = m;
} else {
++l;
}
}
return numbers[l];
}
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。