首页 > 试题广场 >

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

[编程题]在有序旋转数组中找到一个数
  • 热度指数：929 时间限制：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
关于旋转操作：可以简单的理解为把序列从某个位置切成两段然后交换位置
[要求]
期望复杂度为

输入描述:
第一行两个整数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

备注:

算法知识视频讲解
添加回答
offer速来！头像 offer速来！ 
#include<iostream>
#include<vector>
using namespace std;

bool search(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while( left <= right )
    {
        int mid = left + ( right - left ) / 2;

        if( target == nums[mid] )
            return true;
        if( target == nums[left] )
            return true;
        if( target == nums[right] )
            return true;

        // nums[left]、nums[mid]和nums[right]三者相等
        if( nums[left] == nums[mid] && nums[mid] == nums[right] )
        {
            left++;
            right--;
        }
        else if( nums[left] <= nums[mid] )   // 如果前半段有序
        {
            if( nums[left] < target && target < nums[mid] )
                right = mid - 1;
            else
                left = mid + 1;
        }
        else                            // 否则后半段有序
        {
            if( nums[mid] < target && target < nums[right] )
                left = mid + 1;
            else
                right = mid - 1;
        }
    }

    return false;
}

int main(){
    int N, num;
    cin >> N >> num;
    vector<int> arr(N, 0);
    for(int i = 0; i < N; i++){
        cin >> arr[i];
    }
    if(search(arr,num)) cout << "Yes";
    else cout << "No";
    return 0;
}

发表于 2019-09-05 17:03:46 回复(0)
pein531头像 pein531
二分搜索法，主要是确定左边或右边是否有序，以及目标数字是否在子区间内，只要有序且目标存在于其中，就可以接着使用二分。比较坑爹的是这个输入，有时候会存在连续两个空格的情况，搞得我只能用Scanner来读取了。 
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), target = sc.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++)
            arr[i] = sc.nextInt();
        int left = 0, right = n - 1;
        while(left < right) {
            int mid = left + (right - left) / 2;
            if(target == arr[mid] || target == arr[left] || target == arr[right]){
                System.out.println("Yes");     // 找到目标，输出Yes
                return;
            }
            if(arr[mid] <= arr[right]){     // 右边有序
                if(target > arr[mid] && target < arr[right])
                    left = mid + 1;        // 且目标在这个区间当中
                else
                    right = mid - 1;
            }else{
                if(arr[left] < target && arr[mid] > target)
                    right = mid - 1;       //目标在左边
                else
                    left = mid + 1;        // 目标在右边
            }
        }
        System.out.println("No");
    }
}

发表于 2021-06-16 11:25:41 回复(0)
Java
小枫叶666头像 小枫叶666
小米二面时面试官出了这道题，没做对。这个思路是对的，当时我直接二分了😂应该是凉了，不过题目还是要做一下。 
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)
C/C++
nbgao头像 nbgao 
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, m, x;
    bool flag = false;
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>x;
        if(x==m){
            cout<<"Yes"<<endl;
            flag = true;
        }            
    }
    if(!flag)
        cout<<"No"<<endl;
    return 0;
}

发表于 2020-03-28 00:50:44 回复(0)
无心2019头像 无心2019 
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,num;
    cin>>n>>num;
    vector<int>arr(n);
    for(int i=0;i<n;i++)
        cin>>arr[i];
    for(int i=0;i<n;i++)
    {
        if(num==arr[i])
        {
            cout<<"Yes"<<endl;
            return 0;
        }
    }
    cout<<"No"<<endl;
    return 0;
}

发表于 2019-09-06 22:18:14 回复(0)
Java
眼睛想旅行121头像 眼睛想旅行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)
我不是张小白头像 我不是张小白
假酒害人，假算法误人。。。
写了个假算法，啪的一下就过了，很快啊，但是。。。
3 3
3 1 1
就不对劲了，数据弱同样害人啊。
最好还是去 leetcode 上扒原题，试试能不能过吧2333（下面的代码是用来鞭尸的） 
#include <cstdio>

using namespace std;

const int N = 100000;

int n, k;
int a[N];

int main(void) {
    scanf("%d%d", &n, &k);
    for ( int i = 0; i <n; ++i )
        scanf("%d", a + i);
    --n;
    while ( n > 0 && a[n] == a[0] ) --n;
    if ( a[0] == a[n] ) {
        puts( a[0] == k ? "Yes" : "No");
        return 0;
    }
    int l = 0, r = n, m;
    bool flag = false;
    while ( l < r ) {
        m = l + r >> 1;
        if ( a[m] == k ) {
            flag = true;
            break;
        }
        if ( a[m] >= a[0] ) {
            if ( a[l] <= k && k <= a[m] ) r = m;
            else l = m + 1;
        } else {
            if ( k <= a[m] ) r = m;
            else l = m + 1;
        }
    }
    puts( flag ? "Yes" : "No");
    return 0;
}
上面的代码漏了个条件。。。 
#include <cstdio>

using namespace std;

const int N = 100000;

int n, k;
int a[N];

int main(void) {
    scanf("%d%d", &n, &k);
    for ( int i = 0; i <n; ++i )
        scanf("%d", a + i);
    --n;
    while ( n > 0 && a[n] == a[0] ) --n;
    if ( a[0] == a[n] ) {
        puts( a[0] == k ? "Yes" : "No");
        return 0;
    }
    int l = 0, r = n, m;
    while ( l < r ) {
        m = l + r >> 1;
        if ( a[m] == k ) {
            puts("Yes");
            return 0;
        }
        if ( a[m] >= a[0] ) {
            if ( a[l] <= k && k <= a[m] ) r = m;
            else l = m + 1;
        } else {
            if ( k <= a[m] || k > a[n]) r = m;
            else l = m + 1;
        }
    }
    puts( a[r] == k ? "Yes" : "No");
    return 0;
}



编辑于 2020-12-19 12:59:51 回复(0)
Java
牛客380963717号头像 牛客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)
提交观点

问题信息

分治
上传者：小小
难度：
8条回答 3271浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号