目录
- 350-两个数组的交集
- 283-移动零
- 1-两数之和
- 25-K 个一组翻转链表
- 581-最短无序连续子数组
- 合并区间
- 螺旋矩阵
- 数组中相加和为0的三元组
- 数组中出现次数超过一半的数字
- 字符串出现次数的TopK问题
- 206-反转链表
- 160-相交链表
- 19-删除链表的倒数第N个节点
- 21-合并两个有序链表
- 31-下一个排列
- 链表K位翻转
- 链表排序-归并算法
- 判断链表中是否有环
- 设计LRU缓存结构
- 两个链表的第一个公共结点
- 两个链表生成相加链表
- 合并N个有序链表
- 链表内指定区间反转
搜索旋转排序数组-33
访问量:1311
一、简介
整数数组 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 。
题目地址:leetcode
示例 1: 输入:nums = [4,5,6,7,0,1,2], target = 0 输出:4
二、实现
思路:二分查找变种
func search(nums []int, target int) int { if len(nums) == 0 { return -1 } left := 0 right := len(nums) -1 for left <= right { mid := left + (right - left) / 2 if nums[mid] == target { return mid } else if nums[left] < nums[right] { // left -> right 是升序数组 if nums[mid] > target { right = mid -1 } else { left = mid +1 } } else { // left -> right 是两个升序数组 if nums[mid] >= nums[left] { // mid在左半段 if target < nums[0] { left = mid +1 } else if target > nums[0] { if target > nums[mid] { left = mid +1 } else { right = mid -1 } } else { return 0 } } else { // mid在右侧段 if target > nums[len(nums) -1] { right = mid -1 } else if target < nums[len(nums) -1] { if target > nums[mid] { left = mid +1 } else { right = mid -1 } } else { return len(nums) -1 } } } } return -1 }
本文为原创文章,请尊重辛勤劳动,如需转载,请保留本文地址
若您感觉本站文章不错,读后有收获,不妨赞助一下?
我要赞助