Only two more lines code on top of the solution for Part I


  • 17
    S
    public class Solution {
        public int findMin(int[] nums) {
            if (nums == null || nums.length == 0) {
                return Integer.MIN_VALUE;
            }
            
            int start = 0, end = nums.length - 1;
            
            //only need to add the following while loop on top of the solution 
            //for Part I
            //if two line segments have overlap, remove the overlap.
            //so, the problem can be solved as Part I
            while (nums[end] == nums[start] && end > start) {
                end--;
            }
            
            while (start < end) {
                //if the linear monotonically increasing in [start, end]
                if (nums[start] < nums[end]) {
                    return nums[start];
                }
                
                int mid = start + (end - start) / 2;
                if (nums[mid] >= nums[start]) {
                    start = mid + 1;
                }
                else {
                    end = mid;
                }
            }
            
            return nums[start];
        }
    }

  • 1
    X

    Can't understand why people don't use this easy-to-understand method.

    This code works for both Find Minimum in Rotated Sorted Array I and II.

    here is C++ version of your idea.

    class Solution {
    public:
        int findMin(vector<int>& nums) {
            if (nums.empty()) {
                return -1;
            }
            int n = nums.size();
            int left = 0, right = n - 1;
            while (left < right && nums[left] == nums[right]) {
                right -= 1;  // or left += 1; if index is not asked
            }
            // reason:
            // 1. delete only one of the duplicates will not lose min even if duplicates happen to be min
            // 2. make left line > right line, return to the Find Minimum in Rotated Sorted Array I
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (nums[mid] > nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            return nums[left];
        }
    };
    

  • 0
    I

    in the second while loop, the condition nums[mid] > nums[right], can be replaced with nums[mid] >= nums[left], all the other parts still remain the same and it still works. Can anyone tell me the small detail where nums[mid] >= nums[left] needs to have = equals to?

    I am guessing when calculating mid, computer rounds down the integer. so mid might be the same as left.


  • 0
    S

    why does it work?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.