leeetcode33 Search in Rotated Sorted Array

拼搏现实的明天。 2021-12-03 23:17 125阅读 0赞

*  **问题描述**

1.  假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如，数组 \[0,1,2,4,5,6,7\] 可能变为 \[4,5,6,7,0,1,2\] )。搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
2.      本来一个升序数组，截取其前部分放到后面所组成的新数组。有可能截取的部分长度为0，也就是数组还是一个升序数组。

*  **解决思路**

1.  题目提到要求时间复杂为O(lg(n))，首先想到利用二分查找。
2.  找到旋转点。 旋转点代表什么？就是代表数组中最小的那个元素的下标。
3.  再分别对前后两个有序数组进行查找。
    
        1 public class Solution {
         2     public static int search(int[] nums, int target) {
         3         if (nums.length == 0) { return -1;}
         4         int index, start;
         5         start = find_rotate_index(nums, 0, nums.length-1);
         6         // 如果没有旋转
         7         if (start == 0) {
         8             System.out.println("没有旋转");
         9             index = Arrays.binarySearch(nums, target);
        10             return index > -1 ? index : -1;
        11         }
        12 
        13         int[] nums1 = new int[start];
        14         int[] nums2 = new int[nums.length-start];
        15         System.arraycopy(nums, 0, nums1, 0, start);
        16         System.arraycopy(nums, start, nums2, 0, nums.length-start);
        17         if (nums[0] > target) {
        18             index = Arrays.binarySearch(nums2, target);
        19             return index > -1 ? index+start : -1;
        20         }
        21         index = Arrays.binarySearch(nums1, target);
        22         return index > -1 ? index : -1;
        23     }
        24 
        25     public static int find_rotate_index(int[] nums, int left, int right) {
        26         if (left == right || nums[left] < nums[right])
        27             return 0;
        28         while (left <= right) {
        29             int pivot = (left + right) / 2;
        30             if (nums[pivot] > nums[pivot + 1]) {
        31                 System.out.println("pivot + 1");
        32                 return pivot + 1;
        33             }
        34             else {
        35                 if (nums[pivot] < nums[left])
        36                     right = pivot - 1;
        37                 else
        38                     left = pivot + 1;
        39             }
        40         }
        41         return 0;
        42     }
        43 }

转载于:https://www.cnblogs.com/dogeLife/p/11010599.html