首页 > 试题广场 >

在有序旋转数组中找到最小值

[编程题]在有序旋转数组中找到最小值
  • 热度指数：1498 时间限制：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，返回arr中的最小值。
[要求]
期望复杂度为

输入描述:
第一行一个整数N表示数组大小。
接下来N个数表示数组内的数。


输出描述:
输出一个整数表示答案
示例1

输入

7
1 2 3 4 5 6 7

输出

1
示例2

输入

7
4 5 6 7 1 2 3

输出

1

备注:

算法知识视频讲解
添加回答
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[] arr=new int[n];
        for(int i=0;i<n;i++){
            arr[i]=sc.nextInt();
        }
        Arrays.sort(arr);
        System.out.print(arr[0]);
    }
}

发表于 2021-03-25 11:02:53 回复(0)
Java
可以0613头像 可以0613 
import java.util.Scanner;

public class Main {
    public static int find(int p, int r, int n, int arr[]) {
        while (p <= r) {
            int mid = p + (r - p) / 2;
            if (arr[p] <= arr[mid] && arr[mid] <= arr[r]) {
                return (arr[p] <= arr[mid + 1] ? arr[p] : arr[mid + 1]);
            } else if (arr[p] <= arr[mid]) {
                p = mid + 1;
            } else if (arr[mid] <= arr[r]) {
                r = mid - 1;
            }
        }
        return 0;
    }

    public static void main(String[] args) {
        int n = 0;
        int arr[] = new int[10000000];
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        System.out.println(find(0, n - 1, n, arr));
    }
}

发表于 2020-04-05 22:23:52 回复(1)
Java
牛客380963717号头像 牛客380963717号
public class Main {
 public static void main(String[] args) {
  Scanner in = new Scanner(System.in);
  String num_and_len = in.nextLine();
  int num = Integer.valueOf(num_and_len);
  int[] score = new int[num];
  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(find_min(score, 1, a.length));
 }
 public static int find_min(int[] a,int start,int end) {
  if(a[start-1]<a[end-1])
  {return a[start-1];}
  if(start==end) {
   return a[start-1];
  }
  else {
   int mid=(start+end)/2;
   return Math.min(find_min(a, start, mid), find_min(a, mid+1,end ));
  }
  
  
 }
}
发表于 2020-02-17 21:51:27 回复(0)
提交观点

问题信息

分治
上传者：小小
难度：
3条回答 3765浏览

热门推荐

通过挑战的用户

查看代码

相关试题

在有序旋转数组中找到最小值

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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