154 Find Minimum in Rotated Sorted Array II

154. Find Minimum in Rotated Sorted Array II​
1. Question
Follow upfor "Find Minimum in Rotated Sorted Array":
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e.,0 1 2 4 5 6 7might become4 5 6 7 0 1 2).
Find the minimum element.
The array may contain duplicates.
2. Implementation
(1) Binary Search
1
class Solution {
2
    public int findMin(int[] nums) {
3
        int start = 0, end = nums.length - 1, mid = 0;
4
​
5
        while (start + 1 < end) {
6
            mid = start + (end - start) / 2;
7
​
8
            if (nums[mid] > nums[end]) {
9
                start = mid + 1;
10
            }
11
            else if (nums[mid] < nums[end]) {
12
                end = mid;
13
            }
14
            else {
15
                --end;
16
            }
17
        }
18
        return nums[start] < nums[end] ? nums[start] : nums[end];
19
    }
20
}
Copied!
3. Time & Space Complexity
时间复杂度最坏可以是O(n), 平均是log(n), 空间复杂度O(1)

153 Find Minimum in Rotated Sorted Array

162 Find Peak Element

Last modified 2yr ago

Copy link

Contents

154. Find Minimum in Rotated Sorted Array II

1. Question

2. Implementation

3. Time & Space Complexity

154. Find Minimum in Rotated Sorted Array II​

1. Question

2. Implementation

3. Time & Space Complexity

154. Find Minimum in Rotated Sorted Array II