整数数组 nums 按升序排列,旋转后查询某个值

拼搏现实的明天。 2023-10-02 19:24 28阅读 0赞

这是一道常见算法题，leetcode中如下描述：

/**
     * 整数数组 nums 按升序排列，数组中的值 互不相同 。
     *
     * 在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，
     * 使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。
     * 例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
     *
     * 给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
     *
     *  
     *
     * 示例 1：
     *
     * 输入：nums = [4,5,6,7,0,1,2], target = 0
     * 输出：4
     */

解题思路如下：总体采用二分查找思想，然后就是判断条件多一点：

测试代码如下：

public class NandaoSearchInRotatedSortedArray {
    
    	public static void main(String[] args) {
    		int[] nums = {2,3};
    
    		int target = 3;
    		int search = search(nums, target);
    	//	int search2 = search2(nums, target);
    		int search3 = search3(nums, target);
    		//int search1 = search1(nums, target);
    		System.out.println("查到的下标："+search3);
    		//System.out.println("查到的下标："+search1);
    	}
    
    	private static int search3(int[] arr, int num) {
    		int L = 0;
    		int R = arr.length- 1;
    		int M = 0;
    		while (L <= R){
    			M = (L + R) / 2;
    			if(arr[M] == num){
    				return M;
    			}
    			if(arr[L] == arr[M] && arr[M] == arr[R]){
    				if(M == L){
    					L = M + 1;
    					continue;
    				}
    			}
    
    			if(arr[L] != arr[M]){
    				if(arr[M] > arr[L]){
    					if(num >= arr[L] && num < arr[M]){
    						R = M - 1;
    					}else {
    						L = M + 1;
    					}
    				}else {
    					if(num > arr[M] && num <= arr[R]){
    						L = M + 1;
    					}else {
    						R = M - 1;
    					}
    				}
    			}else {
    				if(arr[R] > arr[M]){
    					if(num > arr[M] && num <= arr[R]){
    						L = M + 1;
    					}else {
    						R = M - 1;
    					}
    				}else {
    					if(num >= arr[L] && num < arr[M]){
    						R = M - 1;
    					}else {
    						L = M + 1;
    					}
    				}
    			}
    		}
    
    		return -1;
    	}
    
    }

测试代码思路很清晰，大家认真研读，多尝试coding几次，定会很快掌握。