Header Ad

Leetcode Find Minimum in Rotated Sorted Array II problem solution

In this Leetcode Find Minimum in Rotated Sorted Array II problem solution 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:

  1. [4,5,6,7,0,1,4] if it was rotated 4 times.
  2. [0,1,4,4,5,6,7] if it was rotated 7 times.

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]].

Given the sorted rotated array nums that may contain duplicates, return the minimum element of this array. You must decrease the overall operation steps as much as possible.

Leetcode Find Minimum in Rotated Sorted Array II problem solution


Problem solution in Python.

class Solution:
    def findMin(self, nums: List[int]) -> int:
        i=0
        if not nums:return None
        while(i<len(nums)-1 and nums[i+1]>=nums[i]):
            i+=1
        if i==len(nums)-1:i=-1
        return nums[i+1]



Problem solution in Java.

int low = 0, high = nums.length-1;
        while(low < high) {
            int mid = (low + high) / 2;
            if(nums[low] > nums[mid]) {
                high = mid;
            }else if(nums[mid] > nums[high]) {
                low = mid + 1;
            }else if(nums[low] < nums[mid]){
                return nums[low];
            }else if(nums[mid] < nums[high]) {
                return nums[mid];
            }else {
                low++;
            }
        }
        
        return nums[low];


Problem solution in C++.

int findMin(vector<int>& nums) {
        int left = 0, right = nums.size()-1;
        while (left < right) {
            int mid = left+(right-left)/2;
            if (nums[left] > nums[mid]){ 
                left++;
                right=mid;
            }
            else if (nums[mid] > nums[right]){ 
                left=mid+1;
            }
            else {
                if(nums[left] < nums[right])
                    return nums[left];
                else
                    right--;
            }
        }
        return nums[left];
    }


Problem solution in C.

int findMin(int* nums, int numsSize) {
    if (numsSize == 1 || nums[0] < nums[numsSize-1]) {
        return nums[0];
    }
    for (int i = numsSize - 1; i > 0; i--) {
        if (nums[i] < nums[i-1]) {
            return nums[i];
        }
    }
}




Post a Comment

0 Comments