154. Find Minimum in Rotated Sorted Array II Hard

1/**
2 * [154] Find Minimum in Rotated Sorted Array II
3 *
4 * Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,4,4,5,6,7] might become:
5 * 
6 * [4,5,6,7,0,1,4] if it was rotated 4 times.
7 * [0,1,4,4,5,6,7] if it was rotated 7 times.
8 * 
9 * Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].
10 * Given the sorted rotated array nums that may contain duplicates, return the minimum element of this array.
11 * You must decrease the overall operation steps as much as possible.
12 *  
13 * Example 1:
14 * Input: nums = [1,3,5]
15 * Output: 1
16 * Example 2:
17 * Input: nums = [2,2,2,0,1]
18 * Output: 0
19 *  
20 * Constraints:
21 * 
22 * n == nums.length
23 * 1 <= n <= 5000
24 * -5000 <= nums[i] <= 5000
25 * nums is sorted and rotated between 1 and n times.
26 * 
27 *  
28 * Follow up: This problem is similar to <a href="https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/description/" target="_blank">Find Minimum in Rotated Sorted Array</a>, but nums may contain duplicates. Would this affect the runtime complexity? How and why?
29 *  
30 * 
31 */
32pub struct Solution {}
33
34// problem: https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/
35// discuss: https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/discuss/?currentPage=1&orderBy=most_votes&query=
36
37// submission codes start here
38
39impl Solution {
40    pub fn find_min(nums: Vec<i32>) -> i32 {
41        let (mut start, mut end) = (0, nums.len() - 1);
42        while start < end {
43            let mid = (end - start) / 2 + start;
44            if nums[mid] > nums[end] {
45                start = mid + 1;
46            } else if nums[mid] < nums[end] {
47                end = mid;
48            } else {
49                end -= 1;
50            }
51        }
52        nums[start]
53    }
54}
55
56// submission codes end
57
58#[cfg(test)]
59mod tests {
60    use super::*;
61
62    #[test]
63    fn test_154() {
64        assert_eq!(Solution::find_min(vec![2,2,1,2]), 1);
65        assert_eq!(Solution::find_min(vec![1,2,2,2,2,2]), 1);
66        assert_eq!(Solution::find_min(vec![2,2,2,0,1]), 0);
67        assert_eq!(Solution::find_min(vec![1,2,2,2,3]), 1);
68        assert_eq!(Solution::find_min(vec![2,2,2,3,3,1]), 1);
69    }
70}
71