博罗东莞网站建设,南阳网站改版,app推广代理加盟,怎样自己建设网站题目描述
搜索旋转排序数组
整数数组 nums 按升序排列#xff0c;数组中的值 互不相同 。
在传递给函数之前#xff0c;nums 在预先未知的某个下标 k#xff08;0 k nums.length#xff09;上进行了 旋转#xff0c;使数组变为 [nums[k], nums[k1], ..., num…题目描述
搜索旋转排序数组
整数数组 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-104 nums[i] 104nums 中的每个值都 独一无二题目数据保证 nums 在预先未知的某个下标上进行了旋转-104 target 104
解法
注意旋转后数组的特点
4,5,6,7(最大),0(最小),1,2数组最左边的元素和最右边的元素在原来单调递增的数组中是相邻的数组从左到右先是递增然后到原来有序数组的第一个元素即最小值后又开始递增从原来最小元素为分割点左边的元素一定大于右边所有元素包含最小元素
根据以上特点使用二分查找
旋转后的数组变成两个局部有序的数组 [4,5,6,7] 和 [0,1,2]每次找到mid后先看 mid 为分割位置分割出来的两个部分 [l, mid] 和 [mid 1, r] 哪个部分是有序的并根据有序的那个部分确定我们该如何改变二分查找的上下界 如果中间元素 第一个元素则说明中间元素在左边第一个元素到最大元素之间反之中间元素 最后一个元素则说明中间元素在原来最小元素和现在最右边元素之间
java代码
class Solution {public int search(int[] nums, int target) {int n nums.length;// 如果数组长度为0返回-1if (n 0) {return -1;}// 如果数组长度为1直接比较元素与targetif (n 1) {return nums[0] target ? 0 : -1;}// 左索引从0开始int left 0;// 右索引从末尾n-1开始int right n - 1;// 使用二分查找while (left right) {// 求中间索引值midint mid (left right) / 2;// 如果mid索引对应值等于target返回midif (nums[mid] target) {return mid;}// 如果中间索引值大于等于第一个元素则中间元素在左边第一个元素到最大元素之间if (nums[0] nums[mid]) {// 如果目标值第一个元素 目标值中间元素// 说明目标值在左元素和中间元素之间这部分是有序的右索引mid-1if (nums[0] target target nums[mid]) {right mid -1;} else {// 否则说明目标值在中间元素和最后一个元素之间左索引mid1left mid 1;}} else { // 中间元素在原来最小元素和现在最右边元素之间// 如果目标值最后一个元素 目标值中间元素// 说明目标值在中间元素和最后一个元素之间这部分是有序的左索引mid1if (nums[n-1] target target nums[mid]) {left mid 1;} else {// 否则说明目标值在中间元素和最后一个元素之间左索引mid1right mid -1;}}}return -1;}
}复杂度
时间复杂度O(log(n))其中 n 是数组长度空间复杂度O(1)
