1.1. 题目
1.1.1. 搜索旋转排序数组
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -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
1.1.2. 题解:
- 数组是有序的,不过在一个节点被截断后放到最前面了
- 如果以截断点来说,两个数组 都是增序的
- 然后在数组里找某个值,如果找到返回下标,找不到返回
-1
1.1.3. 思路:
- 因要求时间复杂度 O(logn),数组是有规律的有序的.. 那么二分法是最明显的解决思路
- 我看了下题解, 有个用C++的大佬用的异或.. 以我以往经验,我是想不出来这么牛b的..
- 我的解法很简单
- 既然数组是有规律有序,那么先把数组重新排好 (时间复杂度O(n))
- 然后在排好的数组里二分法查找(O(logn))
- 返回时,按照数组偏移量 加减偏移量 就行了
- 比如
原数组[3,4,5,0,1]转成新数组[0,1,3,4,5] - 那么,查找到0在新数组的下标为
0,原数组分界点在值等于5,下标等于2的位置 - 所以
>=3 && <= 5的数原下标应该是二分法新数组查找的下标 - 数组长度 - 分界点下标 - 1 0,1的偏移量就是二分法新数组查找的下标 + 分界点下标 + 1- 上面减一,下面这个加一,其实分界点求的是下标,下标从0开始..其实偏移量是长度
- 比如
- 时间复杂度 O(n) + O(log n) = max(O(n), O(log n)) = O(log n)
1.1.4. 代码:
点击显示
func search(nums []int, target int) int {
if len(nums) == 0 {
return -1
}
// 先找出 移动的分界点,i是分界点的下标
// 重新排好数组
var i int
for i = range nums {
if i < len(nums) - 1 && nums[i+1] < nums[i] {
nums = append(nums[i+1:],nums[:i+1]...)
break
}
}
// 正常的二分法
m,n := 0,len(nums)-1
for m <= n {
mid := (m + n) / 2
if target < nums[mid] {
n = mid - 1
} else if target > nums[mid] {
m = mid + 1
} else {
// 此处是 根据 判断目标值是在分界点的左边还是右边,返回时加上偏移量
if target <= nums[len(nums) - 1] && target >= nums[len(nums) - i] {
return mid - (len(nums) - i-1)
} else {
return mid + i + 1
}
}
}
return -1
}
// 参考题解的解法的.. 不好理解..
//func search2(nums []int, target int) int {
// m,n := 0,len(nums) - 1
// for m < n {
// mid := (m + n) / 2
// //3,4,5,6,7,0,1,2
// if (nums[0] > target) ^ (nums[0] > nums[mid]) ^ (target > nums[mid]) {
// m = mid + 1
// } else {
// n = mid
// }
// }
// if m == n && nums[m] == target {
// return m
// } else {
// return -1
// }
//}