首页 > 试题广场 >

在有序旋转数组中找到一个数

[编程题]在有序旋转数组中找到一个数

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

有序数组arr可能经过一次旋转处理，也可能没有，且arr可能存在重复的数。例如，有序数组[1, 2, 3, 4, 5, 6, 7]，可以旋转处理成[4, 5, 6, 7, 1, 2, 3]等。给定一个可能旋转过的有序数组arr，再给定一个数num，返回arr中是否含有num

关于旋转操作：可以简单的理解为把序列从某个位置切成两段然后交换位置

[要求]

期望复杂度为 $O(\log n)$

输入描述:

第一行两个整数N, num。分别表示数组大小, 需要找的数。
接下来一行N个整数表示数组内的数。

输出描述:

若num存在于数组中，输出"Yes"，否则输出"No"

示例1

输入

7 7
4 5 6  7 1 2 3

输出

Yes

示例2

输入

7 998244353
4 5 6  7 1 2 3

输出

No

备注:

算法知识视频讲解

Java

眼睛想旅行121

import java.util.Scanner;
import java.util.Arrays;

public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int num=sc.nextInt();
        int[] arr=new int[n];
        for(int i=0;i<n;i++){
            arr[i]=sc.nextInt();
        }
        Arrays.sort(arr);
        System.out.print(isInside(arr,n,num)?"Yes":"No");
    }
    private static boolean isInside(int[] arr, int n, int num) {
        int left = 0;
        int right = n - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (arr[mid] == num) {
                return true;
            }
            if (arr[mid] < arr[right]) {
                if (arr[mid] > num || arr[right] < num) {
                    right = mid - 1;
                } else if (arr[right] == num){
                    return true;
                } else {
                    left = mid + 1;
                }
            } else if (arr[mid] > arr[right]){
                if (arr[mid] < num || arr[left] > num) {
                    left = mid + 1;
                } else if (arr[left] == num) {
                    return true;
                } else {
                    right = mid - 1;
                }
            } else {
                right--;
            }
        }
        return false;
    }
    }

发表于 2021-03-25 12:54:33 回复(0)

Java

小枫叶666

小米二面时面试官出了这道题，没做对。这个思路是对的，当时我直接二分了😂应该是凉了，不过题目还是要做一下。

参考代码：https://blog.csdn.net/fisherming/article/details/80421378?utm_medium=distribute.pc_relevant_t0.none-task-blog-BlogCommendFromMachineLearnPai2-1.add_param_isCf&depth_1-utm_source=distribute.pc_relevant_t0.none-task-blog-BlogCommendFromMachineLearnPai2-1.add_param_isCf

import java.util.*;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
        Scanner scan=new Scanner(System.in);
            while(scan.hasNext())
            {
                    int n=scan.nextInt();
                    int target=scan.nextInt();
                    int[]arr=new int[n];
                    for(int i=0;i<n;i++)
                    {
                            arr[i]=scan.nextInt();
                    }
                    boolean flag=isInarr(arr,target);
                    if(flag)
                            System.out.println("Yes");
                    else
                            System.out.println("No");
            }
	}
        public static boolean isInarr(int[] arr, int key){
        if(arr.length == 0){
            return false;
        }
        int left = 0;
        int right = arr.length - 1;

        while (left < right){
            int mid = left + (right - left)/2;
            if (arr[mid] == key){
                return true;
            }
            //如果前半段有序
            if (arr[mid] > arr[left]){
                //判断Key是否在前半段，如果在，则继续遍历前半段；如果不在，则遍历后半段
                if (arr[mid] > key){
                    right = mid - 1;
                }else {
                    left = mid + 1;
                }
            }
            //如果后半段有序
            if (arr[mid] < arr[right]){
                //判断Key是否在后半段，如果在，则继续遍历后半段；如果不在，则遍历前半段
                if (arr[mid] < key){
                    left = mid + 1;
                }else {
                    right = mid - 1;
                }
            }
        }
        return  false;
    }
}

编辑于 2020-10-05 09:36:17 回复(0)

Java

牛客380963717号

public class Main {
public static void main(String[] args) {
  Scanner in = new Scanner(System.in);
  String num_and_len = in.nextLine();
  String[] temp = num_and_len.split(" ");
  int num = Integer.valueOf(temp[1]);
  int len = Integer.parseInt(temp[0]);
  int[] score = new int[len];
  String aString = in.nextLine();
  aString=aString.replace(" ", " ");
  String[] a = aString.split(" ");
  for (int i = 0; i < a.length; i++) {
   score[i] = Integer.parseInt(a[i]);
  }
  System.out.println(isContain(score, 1, len, num) ? "Yes" : "No");

}

public static boolean isContain(int[] a, int start, int end, int num) {

if (start == end) {

   return a[start-1] == num ? true : false;
  }
  else {
   int mid = (start + end) / 2;
   return isContain(a, start, mid, num)||isContain(a, mid+1, end, num)?true:false;
  }

}
}

发表于 2020-02-17 21:31:01 回复(0)

提交观点

问题信息

分治

上传者：小小

难度：

4条回答 11收藏 4053浏览

通过挑战的用户

查看代码

努力的小石头

2023-03-06 20:36:05
wangyua...

2023-01-10 20:31:42
牛客14363...

2022-09-11 08:49:32
牛客63191...

2022-09-08 20:38:29
DDDVE

2022-09-01 21:34:30

在有序旋转数组中找到一个数

输入描述:

输出描述:

输入

输出

输入

输出

备注:

问题信息

热门推荐

通过挑战的用户

相关试题