导航
导航
文章目录
  1. 题目
  2. 翻译

LeetCode-154.Find Minimum in Rotated Sorted Array II

题目

Follow up for “Find Minimum in Rotated Sorted Array”:
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

The array may contain duplicates.

翻译

 153. Find Minimum in Rotated Sorted Array的跟进:
 如果有重复元素呢?
 会对时间复杂度有影响吗?怎样影响以及为什么?
假设一个有序数组,以一个未知的枢轴旋转了。(例如, 0 1 2 4 5 6 7 可能变为 4 5 6 7 0 1 2 )。
找出数组中的最小元素。
数组中可能有重复元素。

由153. Find Minimum in Rotated Sorted Array方法三改进。
由于存在首尾元素相同的情况,此时若nums[mid]与last相等,无法判断mid在左右哪部分,所以对于这种情况逐个元素排除,令low步进,直到nums[low]与last不等,此时则若nums[mid]与last相等则mid一定在右半部分;或者low与high相等,此时直接返回:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
public int findMin(int[] nums) {
int low = 0, high = nums.length - 1, last = nums[high];
while (low < high) {
if (nums[low] == last) {
low++;
continue;
}
int mid = (high + low) / 2;
if (nums[mid] > last) low = mid + 1;
else if (nums[mid] <= last) high = mid;
}
return nums[high];
}
}