网站备案 暂住证,威宁住房和城乡建设局网站,磁力棒,企业手机网站建设新闻1、算法思路
题目要求必须设计一个时间复杂度为 O(log n) 的算法解决此问题#xff0c;所以我们可以采用二分法。
Step1. 先把 nums[0] 作为目标值#xff0c;通过二分法找到旋转点索引#xff1b;
Step2. 如果旋转点索引为0#xff0c;则数组本身就是升序的#xff0c…1、算法思路
题目要求必须设计一个时间复杂度为 O(log n) 的算法解决此问题所以我们可以采用二分法。
Step1. 先把 nums[0] 作为目标值通过二分法找到旋转点索引
Step2. 如果旋转点索引为0则数组本身就是升序的否则思想上可以将数组一分为二看做两个升序数组。
Step3. 判断 target 目标值在一分为二后的数组的哪一个里面从而确定左右端索引。特殊情况如果旋转点索引为0则左右端索引就是 0 和 nums.length - 1
Step4. 确认了左右端索引之后通过二分法查找到 target 值所在索引若不存在则返回 -1。
2、Java代码实现
public class Search {public static void main(String[] args) {Solution sol new Solution();System.out.println(sol.search(new int[]{4,5,6,7,0,1,2}, 0));//4System.out.println(sol.search(new int[]{4,5,6,7,0,1,2}, 5));//1System.out.println(sol.search(new int[]{1,3,5,7,9}, 3));//1System.out.println(sol.search(new int[]{1,3}, 3));//1System.out.println(sol.search(new int[]{3,1}, 1));//1System.out.println(sol.search(new int[]{8,9,2,3,4}, 9));//1System.out.println(sol.search(new int[]{4,5,6,7,0,1,2}, 3));//-1System.out.println(sol.search(new int[]{1}, 0));//-1System.out.println(sol.search(new int[]{1,3}, 0));//-1}
}// 逐一查找法
//class Solution {
// public int search(int[] nums, int target) {
// for (int i 0; i nums.length; i) {
// if(nums[i] target){
// return i;
// }
// }
// return -1;
// }
//}// 二分查找法
class Solution {public int search(int[] nums, int target) {if (nums.length 1){return nums[0] target ? 0: -1;}// 寻找旋转点的索引int l 1;int r nums.length - 1;while(l r){int mid l r 1;if(nums[mid] nums[0]) l mid;else r --mid;}if(l nums.length - 1){ //旋转点为0时数组依旧是升序排列的l 0;r nums.length - 1;}else if (target nums[0]){r l - 1;l 0;}else if(target nums[nums.length - 1]){r nums.length - 1;}else return -1; //target小于nums[0]又大于nums[n-1]时直接返回-1//target等于两边时直接返回索引if (nums[l] target) return l;if (nums[r] target) return r;// 最后进行二分查找while(l r){int mid l r 1;if(nums[mid] target) return mid;if(nums[mid] target) l mid;else r --mid;}if(nums[l] ! target) return -1;return l;}
}
3、完整题目
整数数组 nums 按升序排列数组中的值 互不相同 。
在传递给函数之前nums 在预先未知的某个下标 k0 k nums.length上进行了 旋转使数组变为 [nums[k], nums[k1], ..., 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) 的算法解决此问题。
示例 1
输入nums [4,5,6,7,0,1,2], target 0
输出4示例 2
输入nums [4,5,6,7,0,1,2], target 3
输出-1
示例 3
输入nums [1], target 0
输出-1提示
1 nums.length 5000-10^4 nums[i] 10^4nums 中的每个值都 独一无二题目数据保证 nums 在预先未知的某个下标上进行了旋转-10^4 target 10^4
