leetcode,33题【搜索旋转排序数组】
2021/11/20 23:10:11
本文主要是介绍leetcode,33题【搜索旋转排序数组】,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
搜索旋转排序数组
- 问题描述
- 测试用例
- 算法
问题描述
整数数组 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)
链接:https://leetcode-cn.com/problems/search-in-rotated-sorted-array
测试用例
示例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
算法
算法思路:如果中间的数小于最右边的数,则右半段是有序的,若中间数大于最右边数,则左半段是有序的,我们只要在有序的半段里用首尾两个数组来判断目标值是否在这一区域内,这样就可以确定保留哪半边了
class Solution { public int search(int[] nums, int target) { int left = 0; int right = nums.length - 1; while(left <= right) { int mid = left + (right - left) / 2; if(nums[mid] == target) { return mid; }else if(nums[mid] < nums[right]) { //右边有序 if(nums[mid] < target && nums[right] >= target) { left = mid + 1; }else { right = mid - 1; } }else { //左边有序 if(nums[mid] > target && nums[left] <= target) { right = mid - 1; }else { left = mid + 1; } } } return -1; } }
这篇关于leetcode,33题【搜索旋转排序数组】的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-04el-table 开启定时器下,表格的选中状态会消失是什么原因-icode9专业技术文章分享
- 2024-10-03如何安装和初始化飞牛私有云 fnOS?-icode9专业技术文章分享
- 2024-10-03如何安装 App 并连接到飞牛 NAS?-icode9专业技术文章分享
- 2024-10-03如何安装飞牛 TV 并连接到影视服务器?-icode9专业技术文章分享
- 2024-10-03如何在PVE和ESXI上安装飞牛私有云 fnOS?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS安装系统异常情况处理-icode9专业技术文章分享
- 2024-10-03飞牛NAS如何创建存储空间?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS硬盘会自动休眠吗?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS如何安装飞牛影视和创建媒体库?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS如何为家人朋友开通影视账号?-icode9专业技术文章分享