Question

Formatted question description: https://leetcode.ca/all/154.html

Follow up for "Find Minimum in Rotated Sorted Array":
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?
Suppose a sorted array 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.

@tag-array

Algorithm

When there are a large number of repeated numbers in the array, the mechanism of binary search will be destroyed, the time complexity of O(lgn) will not be obtained, and the simple and crude O(n) will be returned.

For example, these two situations: {2, 2, 2, 2, 2, 2, 2, 2, 0, 1, 1, 2} and {2, 2, 2, 0, 2, 2, 2, 2, 2, 2, 2, 2}, it can be found that when the first number, the last number, and the middle number are all equal, the binary search method collapses, because it cannot determine whether to go to the left half or the right half.

In this case, move the right pointer one place to the left (or move the left pointer one place to the right) to skip the same number, which will not affect the result, because it just removes the same one, and then affects the remaining part Continue to use the binary search method,

In the worst case, such as all elements of the array are the same, the time complexity will rise to O(n).

Code

public class Find_Minimum_in_Rotated_Sorted_Array_II {

	public class Solution_II {
	    public int findMin(int[] nums) {

	        if (nums == null || nums.length == 0) {
	            return 0;
	        }

	        int low = 0; // left pointer
	        int high = nums.length - 1; // right pointer

		    //  while (low < high) {
	        while (low < high && nums[low] >= nums[high]) { // @note:@memorize: if no "=", failed by [3,1,3]

	        	int mid = low + (high - low) / 2;
	        	System.out.println("mid: " + nums[mid] + ", high: " + nums[high]);
	        	if (nums[mid] > nums[high]) {
	        		low = mid + 1;
	        	} else if (nums[mid] < nums[low]) { // @note: in part-I, only else, no check, but if duplicates, then not working
	        		high = mid; // @note: here, not "high=mid-1"
	        	} else {
	        		right--;
	        	}
	        }

	        return nums[low];
	    }
	}


	public class Solution {
	    public int findMin(int[] nums) {

		        if (nums == null || nums.length == 0) {
		            return 0;
		        }

		        int low = 0; // left pointer
		        int high = nums.length - 1; // right pointer

			    //  while (low < high && nums[low] > nums[high]) {
		        while (low < high && nums[low] >= nums[high]) { // @note:@memorize: if no "=", failed by [3,1,3]

		        	int mid = low + (high - low) / 2;
		        	System.out.println("mid: " + nums[mid] + ", high: " + nums[high]);
		        	if (nums[mid] > nums[high]) {
		        		low = mid + 1;
		        	} else if (nums[mid] < nums[high]) { // @note: in part-I, only else, no check, but if duplicates, then not working
		        		high = mid; // @note: here, not "high=mid-1"
		        	} else {
		        		high--;
		        	}
		        }

		        return nums[low];
	    }
	}
}

############

class Solution {
    public int findMin(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = (left + right) >> 1;
            if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else if (nums[mid] < nums[right]) {
                right = mid;
            } else {
                --right;
            }
        }
        return nums[left];
    }
}

class Solution:
    def findMin(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 1
        while left < right:
            mid = (left + right) >> 1
            if nums[mid] > nums[right]:
                left = mid + 1
            elif nums[mid] < nums[right]:
                right = mid
            else:
                right -= 1
        return nums[left]

############

class Solution(object):
  def findMin(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    ans = nums[0]
    start, end = 0, len(nums) - 1
    while start + 1 < end:
      mid = start + (end - start) / 2
      if nums[start] < nums[mid]:
        start = mid
      elif nums[start] > nums[mid]:
        end = mid
      else:
        start += 1
        ans = min(ans, nums[start])

    return min(ans, nums[start], nums[end])

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

func findMin(nums []int) int {
	left, right := 0, len(nums)-1
	for left < right {
		mid := (left + right) >> 1
		if nums[mid] > nums[right] {
			left = mid + 1
		} else if nums[mid] < nums[right] {
			right = mid
		} else {
			right--
		}
	}
	return nums[left]
}

function findMin(nums: number[]): number {
    let left = 0,
        right = nums.length - 1;
    while (left < right) {
        const mid = (left + right) >> 1;
        if (nums[mid] > nums[right]) {
            left = mid + 1;
        } else if (nums[mid] < nums[right]) {
            right = mid;
        } else {
            --right;
        }
    }
    return nums[left];
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMin = function (nums) {
    let left = 0,
        right = nums.length - 1;
    while (left < right) {
        const mid = (left + right) >> 1;
        if (nums[mid] > nums[right]) {
            left = mid + 1;
        } else if (nums[mid] < nums[right]) {
            right = mid;
        } else {
            --right;
        }
    }
    return nums[left];
};

154 - Find Minimum in Rotated Sorted Array II

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions