首页 > 试题广场 >

在旋转过的有序数组中寻找目标值

[编程题]在旋转过的有序数组中寻找目标值

热度指数：41149 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

有一个长度为 n 的按严格升序排列的整数数组 nums ，在实行 search 函数之前，在某个下标 k 上进行旋转，使数组变为[nums[k],nums[k+1],.....,nums[nums.length-1],nums[0],nums[1],.......,nums[k-1]]。

给定旋转后的数组 nums 和一个整型 target ，请你查找 target 是否存在于 nums 数组中并返回其下标（从0开始计数），如果不存在请返回-1。

数据范围： $0 \le n \le 10000 ， 0 \le target \le 100000$
要求：空间复杂度 $O(1)$ ，时间复杂度 $O(n)$

比如，数组[0,2,4,6,8,10]在下标3处旋转之后变为[6,8,10,0,2,4], 当给定target为10时，10的下标是2，target为3时，nums数组中不存在3，所以返回-1

示例1

输入

[6,8,10,0,2,4],10

输出

说明

如题面解释

示例2

输入

[6,8,10,0,2,4],3

输出

-1

说明

如题面解释

示例3

输入

[2],1

输出

-1

备注:

1 <= nums.length <= 4000

算法知识视频讲解

蒙牛麦片

发表于 2021-07-16 22:29:57

精华题解 NC48 在旋转过的有序数组中寻找目标值题意分析：在数组中查找target 题解一（直接遍历）：直接遍历判断有没有target，有返回下标，没有返回-1；代码实现如下 int search(vector<int> &nums, int target) { for 展开全文

牛客786963925号

发表于 2021-07-14 00:45:17

精华题解解法一：顺序查找顺序查找的思路较为简单：从左至右遍历数组，若找到目标值，返回下标；否则返回-1。实现的代码如下： class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 展开全文

牛一霸

发表于 2021-07-12 21:34:30

精华题解题目：在旋转过的有序数组中寻找目标值描述：给定一个整数数组nums，按升序排序，数组中的元素各不相同。 nums数组在传递给search函数之前，会在预先未知的某个下标t（0 <= t <= nums.length-1）上进行旋转，让数组变为[nums[t], nums[t 展开全文

Gemini48

发表于 2021-07-12 11:31:53

精华题解解法一：暴力 (修正)之前的分析有些错误的地方，没有考虑数组旋转的带来的影响(具体已经在解法二中修正了)。大意的理解为就是给你一个数组和target（目标值）,让寻找与目标值相同的元素并返回对应索引，如果不存在就返回-1；比较典型的二分题目。其实题目中对数组的旋转还是有些坑！！！此类问题，首先想展开全文

未来0116

发表于 2021-07-12 00:01:44

精华题解一.题目描述NC48在旋转过的有序数组中寻找目标值题目链接:https://www.nowcoder.com/practice/87c0e7abcbda41e7963660fa7d020995?tpId=196&&tqId=37078&rp=1&ru=/activit 展开全文

不经历怎么能成长

发表于 2021-05-28 21:27:09

与中间值比较，分前半段有序和后半段有序分别判断。比有序的二分查找多一些判定条件。1、要么前半段有序，要么后半段有序。2、当前半段有序时：即循环数组中间值比循环数组最左边值大则 nums[left] <= nums[mid] 当target 比中间值小，比最左值（前半段最小值）大时，展开全文

南浦草儿

发表于 2021-04-28 21:29:57

let length = nums.length; let j = 1; let key = nums[0]; while(j < length && nums[j] > key){ j++ } if(target > 展开全文

牛客998147552号

发表于 2021-05-24 15:25:23

java版本 import java.util.*; public class Solution { public int search (int[] nums, int target) { // write code here int left = 0; 展开全文

fancycarp

发表于 2021-05-12 19:41:09

先找到翻转的起始下标，通过判断nums[0]与target的相对大小来决定在哪一段上进行常规二分。 class Solution { public: int binary_s(vector<int> nums, int target, int left, int right) 展开全文

An前码后

发表于 2021-07-29 13:39:39

public int search (int[] nums, int target) { // write code here int left =0,right = nums.length-1; while(left<=right){ 展开全文

蘑菇睡不着

发表于 2021-08-15 23:38:17

描述给定一个整数数组nums，按升序排序，数组中的元素各不相同。nums数组在传递给search函数之前，会在预先未知的某个下标 t（0 <= t <= nums.length-1）上进行旋转，让数组变为[nums[t], nums[t+1], ..., nums[nums.lengt 展开全文

whoway

发表于 2021-06-29 16:58:38

一、思路——分情况讨论情况1 情况2 情况3 发现，情况3可以被情况1和2所顺路讨论，代码见后边二、坑点比如：1,3寻找3那么，nums[Right]可能和target相同，见代码中标记的易错点 class Solution { public: /** * 展开全文

萨根的喷火龙

发表于 2021-10-28 13:25:17

就是二分法的使用，只是旋转数组多了一个判断中间mid的值是否大于最左边的值，然后判断从哪里是旋转的。然后再移动left或者right class Solution: def search(self , nums , target ): left = 0 ri 展开全文

梦会绽放

发表于 2022-01-29 16:32:37

思路：二分法我们知道二分法适用于有序数组，并且题中告诉我们数组严格升序，只是经过了旋转，经过一番思考，我们可以充分利用好以上性质，写出让面试官想要的代码。旋转后的数组分为两部分，[low...mid]和[mid...high]，这两部分必有一个是有序数组，我们考虑每次都处理有序的那部分，展开全文

牛客657460335号

发表于 2021-08-21 20:53:53

//对应leetcode的,面试题 10.03. 搜索旋转数组,解析见leetcodepublic class Solution { public int search(int[] arr, int target) { int n = arr.length; int 展开全文

问题信息

二分

上传者：牛客301499号

难度：

67条回答 331收藏 2909浏览

通过挑战的用户

不想上班螺狮粉在炒股

2023-02-07 17:17:02
在冲浪的ssr很主动

2022-09-19 22:04:38
Flawles...

2022-09-16 11:34:12
牛客11626...

2022-09-16 11:20:37
牛客67565...

2022-09-16 10:04:29

在旋转过的有序数组中寻找目标值

输入

输出

说明

输入

输出

说明

输入

输出

备注:

问题信息

热门推荐

通过挑战的用户

相关试题