解题报告 - 搜索旋转排序数组
LeetCode 搜索旋转排序数组
@TOC
题目描述
整数数组
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
。你必须设计一个时间复杂度为
O(log n)
的算法解决此问题。
示例:
输入:nums = [4,5,6,7,0,1,2], target = 0 输出:4
提示:
1 <= nums.length <= 5000
-104 <= nums[i] <= 104
nums 中的每个值都 独一无二
题目数据保证 nums 在预先未知的某个下标上进行了旋转
-104 <= target <= 104
一、解题关键词
旋转数组
查找问题
二、解题报告
1.思路分析
- 二分思路(数组部分有序)
- 也可以使用hash表
- 二分解法 就是经典的 left right mid 注意控制边界
2.时间复杂度
3.代码示例
class Solution {
//数组有序 且 不重复
//转String 直接 截取 拼接
public int search(int[] nums, int target) {
if (null == nums || nums.length < 1) return -1;
int len = nums.length;
int left = 0;
int right = len - 1;
int mid;
Map<Integer,Integer> map = new HashMap();
for (int i = 0; i < nums.length; i++) {
map.put(nums[i],i);
}
Integer res = (Integer)map.getOrDefault(target, -1);
// while (left <= right) {
// mid = left + (right - left) / 2;
// //先做限制
// if (nums[mid] == target){
// return mid;
// }
// //前半部分有序
// if (nums[left] <= nums[mid]){
// //target 在前半部分
// if (target >= nums[left] && target < nums[mid]){
// right = mid - 1;
// }else{
// left = mid + 1;
// }
// }else {
// if (target <= nums[right] && target > nums[mid]){
// left = mid + 1;
// }else{
// right = mid - 1;
// }
// }
// }
return res;
}
}
4.知识点
二分 & hash表
注意控制数据边界
数组只要有序 一定要联想到二分,下面是二分的经典模版
int left = 0, right = n - 1;
while(left <=right){
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
网友评论