Share a Neat Recursive Solution


  • 0
    H
    class Solution {
    public:
        int findMin(vector<int>& nums) {
            int n = nums.size();
            if (!n) return 0;
            return findMin(nums, 0, n - 1);
        }
        
        int findMin(vector<int>& nums, int begin, int end) {
            if (begin >= end - 1) return min(nums[begin], nums[end]);
            int mid = (begin + end) / 2;
            if (nums[begin] > nums[mid - 1]) return findMin(nums, begin, mid - 1);
            if (nums[mid + 1] > nums[end]) return findMin(nums, mid + 1, end);
            if (nums[mid - 1] > nums[mid + 1]) return min(nums[mid], nums[mid + 1]);
            return nums[begin];
        }
    };
    
    /**
     *  Rotations can be grouped into five situations:
     *  1   2   4   5   6   7   0   // pivot in right
     *  7   0   1   2   4   5   6   // pivot in left
     *  
     *  4   5   6   7   0   1   2   // pivot next to mid
     *  5   6   7   0   1   2   4   // pivot is mid
     *  
     *  0   1   2   4   5   6   7   // no rotation
     */

Log in to reply
 

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