首页 > 编程语言(其他) > 个人记录-LeetCode 81. Search in Rotated Sorted Array II

个人记录-LeetCode 81. Search in Rotated Sorted Array II

2017年1月10日 发表评论 阅读评论

问题:
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Write a function to determine if a given target is in the array.

The array may contain duplicates.

代码示例:
1、上神器

public class Solution {
    public boolean search(int[] nums, int target) {
        Set<Integer> set = new HashSet<>();
        for (int i : nums) {
            set.add(i);
        }
        return set.contains(target);
    }
}

2、分段讨论
将原来升序数组的后一部分,移动到了前面,可按下列方式二分法处理:

public class Solution {
    public boolean search(int[] nums, int target) {
        int start = 0, end = nums.length - 1, mid = -1;

        while(start <= end) {
            mid = (start + end) / 2;

            if (nums[mid] == target) {
                return true;
            }

            //右边是排序的或左侧是未排序的
            if (nums[mid] < nums[end] || nums[mid] < nums[start]) {
                if (target > nums[mid] && target <= nums[end]) {
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
                //左边是排序的或右侧是未排序的
            } else if (nums[mid] > nums[start] || nums[mid] > nums[end]) {
                if (target < nums[mid] && target >= nums[start]) {
                    end = mid - 1;
                } else {
                    start = mid + 1;
                }
                //重复部分,++start或--end均可
            } else {
                end--;
            }
        }
        return false;
    }
}
作者:Gaugamela 发表于2017/1/10 21:07:37 原文链接
阅读:289 评论:0 查看评论
分类: 编程语言(其他) 标签: