leetcode----81. Search in Rotated Sorted Array II

連結：

https://leetcode.com/problems/search-in-rotated-sorted-array-ii/

大意：

給定一個旋轉有序一維數組nums，判斷target是否在nums中。注意：nums中含重複的元素。例子：

思路：

本題思路和leetcode33題類似：https://blog.csdn.net/smart_ferry/article/details/88775716

不過在送出code後擊敗率低得可憐，确實，之前的解法是O（n）的時間複雜度

代碼：（非最佳）

class Solution {
    public int search(int[] nums, int target) {
        if(nums.length == 0 || nums.length == 1 && nums[0] != target)
            return -1;
        int s = 0, e = nums.length - 1;
        if (target > nums[e] && target < nums[s])
            return -1;
        if (target <= nums[e]) {
            while (e > s && nums[e - 1] < nums[e] && target < nums[e]) {
                e--;
            }
            if (nums[e] == target)
                return e;
            else 
                return -1;
        } else {
            while (s < e && nums[s] < nums[s + 1] && target > nums[s]) {
                s++;
            }
            if (nums[s] == target)
                return s;
            else 
                return -1;
        }
    }
}
           

結果：

結論：

思路有待優化。回想下XXY大佬給我講解的一個秀的解法。