Leetcode 154. Find Minimum in Rotated Sorted Array II

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:

Difficulty:Hard

Category:

Analyze

Solution

class Solution {
 public:
  int findMin(vector<int>& nums) {
    int left = 0, right = nums.size() - 1, ans = nums[0];
    if (nums[left] < nums[right]) return nums[0];

    while (left < right - 1) {
      int mid = left + (right - left) / 2;

      // If the mid value > left value, then move the right part search.
      if (nums[left] < nums[mid]) {
        ans = min(ans, nums[left]);
        left = mid;
      }
      else if (nums[left] > nums[mid]) right = mid;
      else ++left;
    }
    return min(ans, min(nums[left], nums[right]));
  }
};

Solution 2: Divide and conquer

cite: 花花酱 LeetCode 154. Find Minimum in Rotated Sorted Array II

Time complexity:

  • Average: O(log n)
  • Worst: O(n)

Space complexity: O(1)

// Author: Huahua
class Solution {
public:
    int findMin(vector<int> &num) {
        return findMin(num, 0, num.size()-1);
    }

    int findMin(const vector<int>& num, int l, int r)
    {
        // One or two elements, solve it directly
        if (l+1 >= r) return
            min(num[l], num[r]);

        // Sorted
        if (num[l] < num[r])
            return num[l];

        int m = l + (r-l)/2;

        // Recursively find the solution
        return min(findMin(num, l, m - 1),
                   findMin(num, m, r));
    }
};
By guozetang            Updated: 2020-09-19 13:02:30

results matching ""

    No results matching ""