Help ! Duplicate Rotation Position find error .....


  • 0
    2

    My bug is caused by the previous problem as we can not find the accurate position of the min-val in the rotated array with duplicates.

    My code can not pass the cases ...

     [1,1,3,1]
    

    As the the find function can not find the rotated position "3"...........

    I hope you can help me .

    The related question has been posted at :

    https://leetcode.com/discuss/89446/most-posted-solution-is-wrong-in-fact-the-test-cases-are-weak

    class Solution {
    public:
        bool search(vector<int>& nums, int target) {
            int pos = findMin(nums);
            int index = binarySearch(nums, target, pos);
            return nums[index] == target ? true : false;
        }
        
        int findMin(vector<int> &nums) {
            int start = 0, end = nums.size() - 1;
            while(end > start) {
                int mid = (start + end) / 2;
                if(nums[mid] > nums[end])  start = mid + 1;
                else if(nums[mid] < nums[end]) end = mid;
                else end--;
            }
            return end;
        }
        
        int binarySearch(vector<int>& nums, int target, int pos) {
            int left = 0, right = nums.size();
            int size_nums = nums.size();
            while(right - left > 1){
                int mid = (left + right) / 2;
                if(nums[(mid+pos)%size_nums] > target)  right = mid;
                else left = mid;
            }
            return (left + pos) % size_nums;
        }
    };
    

Log in to reply
 

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