首页 > 编程语言 > 详细

LeetCode 33 搜索旋转排序数组(Java)

时间:2018-09-22 14:18:14      阅读:203      评论:0      收藏:0      [点我收藏+]

技术分享图片

技术分享图片

技术分享图片

思路:按照上图两种情形分别进行二分查找

public int search(int[] nums, int target) {
    if(nums==null||nums.length<1) return -1;
    int left = 0;
    int right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) return mid;
        //条件1
        if (nums[mid] >= nums[left]) {
            if (target < nums[mid] && target >= nums[left]) {
                right = mid - 1;
            }else {
                left = mid + 1;
            }
        }
        //条件2
        if (nums[mid] <= nums[right]) {
            if (target > nums[mid] && target <= nums[right]) {
                left = mid + 1;
            }else {
                right = mid - 1;
            }
        }
    }
    return -1;
}

LeetCode81 搜索旋转排序数组题目的延伸,本题中的 nums 可能包含重复元素。

  • 这种情况下只需要举出能够最坏情况的数据是 [1,1,1,1... 1] 里有一个0即可。
  • 在这种情况下是无法使用二分法的,复杂度是O(n)
  • 因此写个for循环最坏也是O(n),那就写个for循环就好了。
public boolean search(int[] A, int target) {
    for (int i = 0; i < A.length; i ++) {
        if (A[i] == target) {
            return true;
        }
    }
    return false;
}

LeetCode 33 搜索旋转排序数组(Java)

原文:https://www.cnblogs.com/keeya/p/9689927.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!