每日题解:LeetCode 33. 搜索旋转排序数组

题目地址

题目描述

已知一个长度为 n 的数组,预先按照升序排列,经由 1 到 n 次 旋转 后,得到输入数组。例如,原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到:
若旋转 4 次,则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次,则可以得到 [0,1,2,4,5,6,7]
注意,数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个元素值 互不相同 的数组 nums ,它原来是一个升序排列的数组,并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

 

示例 1:

输入:nums = [3,4,5,1,2]
输出:1
解释:原数组为 [1,2,3,4,5] ,旋转 3 次得到输入数组。
示例 2:

输入:nums = [4,5,6,7,0,1,2]
输出:0
解释:原数组为 [0,1,2,4,5,6,7] ,旋转 4 次得到输入数组。
示例 3:

输入:nums = [11,13,15,17]
输出:11
解释:原数组为 [11,13,15,17] ,旋转 4 次得到输入数组。

提示:

n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
nums 中的所有整数 互不相同
nums 原来是一个升序排序的数组,并进行了 1 至 n 次旋转

解法

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

    int left=0,right=len-1;
    while(left<=right){
        int mid = (left + right) >>1;
          if (nums[mid] == target) {
                return mid;
            }
            if(nums[left]<= nums[mid]){
                if (target >= nums[left] && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }else{
                if(nums[mid] < target && target <= nums[len-1]){
                        left = mid + 1;
                }else{
                     right = mid - 1;
                }
            }

    }
    return -1;
}
 }

解题思路

二分法

根据题意:数组在进行旋转后局部是有序的,这样查找有序数组某个元素,使用二分法便可以了
但是,数组是局部有序,所以当查找到nums[mid]时,在[L, mid] 和 [mid + 1, R] 两个部分时,我们需要确认二分查找的上下界

  1. 如果 [L, mid - 1] 是有序数组,且 nums[L]<target <nums[mid]的大小搜索范围在 [L, mid - 1]
  2. 如果 [mid, R] 是有序数组,且 nums[mid+1]<target <nums[R],则应该将搜索范围在 [mid + 1, R]
 if (nums[left] <= nums[mid]) {
	if (target >= nums[left] && target < nums[mid]) {
    		right = mid - 1;
	} else {
    		left = mid + 1;
	}	
}else{
	if(nums[mid] < target && target <= nums[len-1]){
		left = mid + 1;
	}else{
		right = mid - 1;
}

然后就是二分法的模板

 while(left<=right){
	int mid = (left + right) >>1;
	if (nums[mid] == target) {
	return mid;
	}
//条件的进行范围缩进
}
最近的文章

每日题解:LeetCode 264. 丑数 II

题目地址题目描述给你一个整数n,请你找出并返回第n个丑数。丑数就是只包含质因数2、3和/或5的正整数。示例1:输入:n=10输出:12解释:[1,2,3,4,5,6,8,9,10,12]是由前10个丑数组成的序列。示例2:输入:n=1输出:1解释:1通常被视为丑数。解法classSolution{p…

继续阅读
更早的文章

每日题解:LeetCode 263. 丑数

题目地址题目描述给你一个整数n,请你判断n是否为丑数。如果是,返回true;否则,返回false。丑数就是只包含质因数 2、3和/或 5 的正整数。 示例1:输入:n=6输出:true解释:6=2×3示例2:输入:n=8输出:true解释:8=2×2×2示例3:输入:n=14输出:false解释:1…

继续阅读