154. Find Minimum in Rotated Sorted Array II.md

154. Find Minimum in Rotated Sorted Array II

---

leetcode-cn Daily Challenge on July 22th, 2020.link

leetcode-cn Daily Challenge on April 9th, 2021.

leetcode Daily Challenge on July 25th, 2020.

---

Difficulty : Hard

Related Topics : Array、Binary Search

---

Suppose an array sorted in ascending order 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.

Example 1:

Input: [1,3,5]
Output: 1

Example 2:

Input: [2,2,2,0,1]
Output: 0

Note:

• This is a follow up problem to Find Minimum in Rotated Sorted Array.
• Would allow duplicates affect the run-time complexity? How and why?

---

Solution

• mine
  • Java

    • Binary Search Runtime: 1 ms, faster than 38.47%, Memory Usage: 40.9 MB, less than 5.03% of Java online submissions

      // O(logN)time
      // O(1)space
      public int findMin(int[] nums) {
          int l = 0, r = nums.length - 1;
          while(l < r){
              int mid = (l + r) >> 1;
              if(nums[mid] < nums[r]){
                  r = mid;
              }else if(nums[mid] > nums[r]){
                  l = mid + 1;
              }else{
                  r--;
              }
          }
          return nums[l];
      }
      

    • Sort Runtime: 2 ms, faster than 38.47%, Memory Usage: 41.6 MB, less than 5.03% of Java online submissions

      // O(N*logN)time
      // O(N)space
      public int findMin(int[] nums) {
          Arrays.sort(nums);
          return nums[0];
      }
      

---

• the most votes

• Binary Search Runtime: 1 ms, faster than 38.47%, Memory Usage: 40.7 MB, less than 5.03% of Java online submissions

  // O(logN)time
  // O(1)space
  public int findMin(int[] nums) {
      int lo = 0, hi = nums.length - 1;
      while (lo < hi) {
          int mi = lo + (hi - lo) / 2;
          if (nums[mi] > nums[hi]) {
              lo = mi + 1;
          } else if (nums[mi] < nums[lo]) {
              hi = mi;
              lo++;
          } else { // nums[lo] <= nums[mi] <= nums[hi] 
              hi--;
          }
      }
      return nums[lo];
  }
  

---