时间空间复杂度都是O(N)
在转动过的有序数组中寻找目标值
http://www.nowcoder.com/questionTerminal/7cd13986c79d4d3a8d928d490db5d707
我的空间复杂度是O(N) 没有用到转动的特点
import java.util.*;
public class Solution {
/**
*
* @param A int整型一维数组
* @param target int整型
* @return int整型
*/
public int search (int[] A, int target) {
// write code here
// 如果先存储元素+下标，再改成有序的，取到目标值之后去哈希表找到对应的下标返回即可
Map<Integer,Integer> map = new HashMap<>();
for(int i = 0; i < A.length; i++){
map.put(A[i],i);
}
Arrays.sort(A);
int left = 0;
int right = A.length-1;// 这里注意已经提示不存在重复值
while(left <= right){
int mid = left + (right - left)/2;
if(A[mid] == target) return map.get(A[mid]);
if(A[mid] > target) right = mid-1;
if(A[mid] < target) left = mid+1;
}
return -1;
}
}
查看11道真题和解析