LeetCode每日一题

1. Search in Rotated Sorted Array

Medium

5959518Add to ListShare

You are given an integer array nums sorted in ascending order, and an integer target.

Suppose that nums 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]).

If target is found in the array return its index, otherwise, return -1.

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Example 3:

Input: nums = [1], target = 0
Output: -1

Constraints:

• 1 <= nums.length <= 5000
• -10^4 <= nums[i] <= 10^4
• All values of nums are unique.
• nums is guranteed to be rotated at some pivot.
• -10^4 <= target <= 10^4

主要代码

class Solution {
    public int search(int[] nums, int target) {
         if (nums.length == 1) {
            if (nums[0] == target) {
                return 0;
            } else {
                return -1;
            }
        }

        //1. 找到分割点
        int len = nums.length;
        int tmp = 0;
        for (int i = 1; i < len; i++) {
            if (nums[i] < nums[i - 1]) {
                tmp = i;
            }
        }

        int l = 0, r = tmp - 1;
        while (l < r) {
            int mid = (l + r) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        if (nums[l] == target) {
            return l;
        }

        l = tmp;
        r = len - 1;

        while (l < r) {
            int mid = (l + r) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }

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


        return -1;
    }
}