81. Search in Rotated Sorted Array II

题目描述和难度

  • 题目描述：

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。

编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。

示例 1:

输入: nums = [2,5,6,0,0,1,2], target = 0
输出: true

示例 2:

输入: nums = [2,5,6,0,0,1,2], target = 3
输出: false

进阶:

  • 这是 搜索旋转排序数组 的延伸题目，本题中的 nums  可能包含重复元素。
  • 这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？

思路分析

求解关键：

参考解答

参考解答1

public class Solution {

    public boolean search(int[] nums, int target) {
        int len = nums.length;
        if (len == 0) {
            return false;
        }
        int left = 0;
        int right = len - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            // System.out.println(mid);
            if (nums[mid] == target) {
                return true;
            }
            // 10 11 4 5 6 7 8 9
            if (nums[mid] < nums[right]) {
                // 右边的一定是顺序数组
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            } else {
                assert nums[mid] >= nums[right];
                // 5 1 2 3 4 5 5 5 5 5 5 5
                // 1 1 3 1
                // 可能在左边，也有可能在右边
                if (nums[mid] == nums[right]) {
                    // 一步一步来，这一步操作很关键，因为我们已经判断了 nums[mid] != target，而此时 nums[mid] == nums[right]，
                    // 所以，nums[right] 可以丢弃了
                    right--;
                } else {
                    assert nums[mid] > nums[right];
                    // 4 5 6 7 8 9 1 2
                    // 左边是顺序数组
                    if (nums[left] <= target && target < nums[mid]) {
                        right = mid - 1;
                    } else {
                        left = mid + 1;
                    }
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {1, 1, 3, 1};
        int target = 3;
        boolean search = solution.search(nums, target);
        System.out.println(search);
    }
}

本篇文章的地址为 https://liweiwei1419.github.io/leetcode-solution/leetcode-0081-search-in-rotated-sorted-array-ii ，如果我的题解有错误，或者您有更好的解法，欢迎您告诉我 liweiwei1419@gmail.com 。