import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型一维数组 * @param target int整型 * @return int整型 */ public int search (int[] nums, int target) { //找到k int k = findK(nums) ; //先还原数组(三次反转) reverse(nums , 0 , k - 1) ; reverse(nums , k , nums.length - 1) ; reverse(nums , 0 , nums.length - 1) ; //二分查找 int idx = binarySearch(nums , 0 , nums.length - 1 , target) ; //坐标映射(将原数组中的元素位置映射成旋转后的数组的位置) return idx == -1 ? -1 : (idx + k) % nums.length ; } //二分查找 public int binarySearch(int[] arr , int s , int e , int t) { while(s <= e) { int m = s + (e - s) / 2 ; if(arr[m] == t) { return m ; } else if(arr[m] < t) { s = m + 1 ; } else { e = m - 1 ; } } return -1 ; } //找到旋转数组的分界点 public int findK(int[] arr) { for(int i = 0 ; i < arr.length - 1 ; i ++) { if(arr[i + 1] < arr[i]) { return i + 1 ; } } return 0 ; } //在s-e的范围翻转 public void reverse(int[] arr , int s , int e) { while(s < e) { int t = arr[s] ; arr[s] = arr[e] ; arr[e] = t ; s ++ ; e -- ; } } }