首页 > 试题广场 >

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

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

热度指数：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

算法知识视频讲解

Java

OOOWen

import java.util.*;
public class Solution {
    public int search (int[] nums, int target) {
        // 用哈希暂存当前的标号
        HashMap<Integer,Integer> hm = new HashMap<>();
        for(int i =0; i<nums.length; i++){
            hm.put(nums[i],i);
        }
        //重新排序
        Arrays.sort(nums);
        //二分查询
        int x1 = Arrays.binarySearch(nums, target);
        if(x1<0){
            return -1;
        }else{
            return hm.get(nums[x1]);
        }
    }
}

发表于 2022-06-24 12:20:47 回复(0)

Java

Carmen-Xiao

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @param target int整型 
     * @return int整型
     */
public int search (int[] nums, int target) {
        int left = 0, right = nums.length -1;
        while (left <= right){
            int mid = left + (right - left) /2;
            if(nums[mid] == target){
                return mid;
            }else if(nums[mid] >= nums[left]){//前半段有序时：即循环数组中间值比循环数组最左边值大 
                if(nums[left] <= target && target<nums[mid]){//当target 比中间值小
                    right=mid-1;
                }else{
                    left=mid+1;
                }
            }else {// 前半段无序，后半段有序 mid到right
                if(target <= nums[right] && target<nums[mid]){
                    right=mid-1;
                }else{
                    left=mid+1;
                }
            }
        }
        return -1;
    }
}

发表于 2021-11-22 18:55:45 回复(0)

Java

小灰灰QAQ

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @param target int整型 
     * @return int整型
     */
   public static int search(int[] nums, int target) {
        int l = 0;
        int r = nums.length - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] == target)
                return mid;
            if (nums[mid] >= nums[l]) {
                if (target > nums[mid])
                    l = mid + 1;
                else if (target < nums[mid]) {
                    if (target < nums[l])
                        l = mid + 1;
                    else if (target > nums[l])
                        r = mid - 1;
                    else {
                        return l;
                    }
                } else {
                    return mid;
                }
            } else {
                if (target > nums[mid]) {
                    if (target < nums[r]) {
                        l = mid + 1;
                    } else if (target > nums[r]) {
                        r = mid - 1;
                    } else {
                        return r;
                    }
                } else if (target < nums[mid]) {
                    r = mid - 1;
                } else {
                    return mid;
                }
            }
        }
        return -1;
    }
}

画一张图分类讨论，还是二分法。

发表于 2021-11-22 09:58:17 回复(0)

Java

z201902151517890

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @param target int整型 
     * @return int整型
     */
    public int search (int[] nums, int target) {
        // write code here
        int l = 0;
        int r = nums.length - 1;
        while(l < r){
            int mid = l + r >> 1;
            if(nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        return nums[l] == target ? l : -1;
    }
}

发表于 2021-08-21 19:48:35 回复(2)

Java

shine0801

 
//说好的二分法呢？
public int search (int[] nums, int target) {
        // write code here
         for (int i = 0; i < nums.length; i++) {
            if(nums[i] == target)
                return i ;
        }
        return -1;
    }

发表于 2021-06-25 09:19:06 回复(0)

Java

牛客507555376号

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @param target int整型 
     * @return int整型
     */
    public int search (int[] nums, int target) {
        if(nums==null||nums.length==0){
            return -1;
        }
        if(nums.length==1){
            return nums[0]==target?0:-1;
        }
        int loc;
        for(loc = 1;loc<nums.length;++loc){
            if(nums[loc-1]>nums[loc]){
                break;
            }
        }
        if(loc==nums.length){
            return binarySearch(nums,0,loc-1,target);
        }
        
        int res;
        if(target>=nums[0]){
            res = binarySearch(nums,0,loc,target);
        }else{
            res = binarySearch(nums,loc,nums.length-1,target);
        }
        return res;
    }
    
    private int binarySearch(int[] arr,int start,int end,int target){
        int mid;
        while(start<=end){
            mid = start+(end-start)/2;
            if(arr[mid]==target){
                return mid;
            }else if(arr[mid]>target){
                end = mid -1;
            }else{
                start = mid +1;
            }
        }
        return -1;
    }
}

发表于 2021-06-04 19:56:29 回复(0)

Java

Mono_Chrome

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @param target int整型 
     * @return int整型
     */
    public int search (int[] nums, int target) {
        // write code here
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] >= nums[left]) {
                if (target >= nums[left] && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                if (target <= nums[right] && target > nums[mid]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
}

发表于 2021-05-17 20:26:08 回复(0)

Java

惠灵顿靖

    public int search (int[] nums, int target) {
        for(int i=0;i<nums.length;i++){
            if(nums[i]==target)
                return i;
        }
        return -1;
    }

发表于 2021-04-29 14:20:27 回复(1)

Java

每日一刷

1.利用HashMap

import java.util.*;
public class Solution {
    public int search (int[] nums, int target) {
        // write code here
        HashMap<Integer,Integer> hm = new HashMap<>();
        for(int i =0; i<nums.length; i++){
            hm.put(nums[i],i);
        }
        Arrays.sort(nums);
        int left = 0, right= nums.length-1;
        while(left<=right){
            int mid = left+(right - left)/2;
            if(nums[mid] == target) return hm.get(nums[mid]);
            if(nums[mid] > target)right = mid-1;
            if(nums[mid] < target)left = mid+1;
        }
        return -1;
    }
}

2.直接二分

import java.util.*;
public class Solution {
    public int search (int[] nums, int target) {
        // write code here
        int lo=0,hi=nums.length-1;
        while(lo <= hi){
            int mid = lo+ (hi-lo)/2;
            if(nums[mid] == target) return mid;
            if(nums[mid] <nums[hi] && nums[mid]<target && target<=nums[hi])
                lo = mid+1;
            else if(nums[mid] >nums[hi] &&!( nums[lo] <=target && target < nums[mid]))
                lo = mid+1;
            else
                hi = mid-1;
        }
        return -1;
    }
}

编辑于 2021-04-26 11:39:16 回复(8)

提交观点

问题信息

二分

上传者：牛客301499号

难度：

13条回答 331收藏 2917浏览

通过挑战的用户

不想上班螺狮粉在炒股

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

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

输入

输出

说明

输入

输出

说明

输入

输出

备注:

1.利用HashMap

2.直接二分

问题信息

热门推荐

通过挑战的用户

相关试题