Just modify one line can solve both I and II


  • 0
    J

    public class Solution {
    public boolean search(int[] nums, int target) {
    if (nums == null || nums.length == 0) {
    return false;
    }
    int left = 0, right = nums.length - 1;
    while (left + 1 < right) {
    while (left + 1 < right && nums[left] == nums[right]) right--; // The rest code is the same with Search in Rotated Sorted Array I, I only add this line, so if there are duplicates, in the worst case time comlexity becomes O(n)
    int mid = left + (right - left) / 2;
    if (nums[mid] == target) {
    return true;
    }
    if (nums[mid] >= nums[left]) {
    if (target <= nums[mid] && target >= nums[left]) {
    right = mid;
    } else {
    left = mid;
    }
    } else {
    if (target >= nums[mid] && target <= nums[right]) {
    left = mid;
    } else {
    right = mid;
    }
    }
    }
    if (nums[left] == target || nums[right] == target) {
    return true;
    }
    return false;
    }
    }


  • 0
    J
    public class Solution {
        public boolean search(int[] nums, int target) {
            if (nums == null || nums.length == 0) {
                return false;
            }
            int left = 0, right = nums.length - 1;
            while (left + 1 < right) {
                while (left + 1 < right && nums[left] == nums[right]) right--; // The rest code is the same with Search in Rotated Sorted Array I, I only add this line, so if there are duplicates, in the worst case time comlexity becomes O(n)
                int mid = left + (right - left) / 2;
                if (nums[mid] == target) {
                    return true;
                }
                if (nums[mid] >= nums[left]) {
                    if (target <= nums[mid] && target >= nums[left]) {
                        right = mid;
                    } else {
                        left = mid;
                    }
                } else {
                    if (target >= nums[mid] && target <= nums[right]) {
                        left = mid;
                    } else {
                        right = mid;
                    }
                }
            }
            if (nums[left] == target || nums[right] == target) {
                return true;
            }
            return false;
        }
    }
    

Log in to reply
 

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