旋转数组中的最小元素

[编程题]旋转数组中的最小元素

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

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个排好序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转，该数组的最小值为1。

输入描述:

一个排好序的数组的一个旋转
数组长度不超过1000000

输出描述:

该数组的最小值

示例1

输入

3 4 5 1 2

输出

算法知识视频讲解

Java

牛客886618438号

import java.util.Scanner;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main{
    public static void main(String[] args) throws IOException{
        //Scanner sc=new Scanner(System.in);//超时
        //String s=sc.nextLine();
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String s=br.readLine();
        String[] ss=s.split(" ");
        int[] array=new int[ss.length];
        for(int i=0;i<array.length;i++){
            array[i]=Integer.parseInt(ss[i]);
        }
        System.out.println(getMin2(array));
    }
//法一
    public static int getMin2(int[] array){
        if(array==null){
                return 0;
            }
        if(array.length==1){
            return array[0];
        }else{
            int j=0;
            for(int i=0;i<array.length-1;i++){
                if(array[i+1]<array[i]){
                	j=i+1;
                     break;
               }
          }
            return array[j];
        }
    }
      
//法二
  
    public static int getMin(int[] array){
        if(array==null){
                return 0;
            }
        int start=0;
        int end=array.length-1;
        int mid=0;
        while(start<end){
            if(start==end-1){
                if(array[start]<array[end]){
                    return array[start];
                }else{
                    return array[end];
                }
            }else{
                mid=(start+end)/2;
                if(array[mid]<array[start]){
                    end=mid;
                }else if(array[mid]>array[end]){
                    start=mid+1;
                }else{
                    int min=array[start];
                    for(int i=start+1;i<end;i++){
                        if(min>array[i]){
                            min=array[i];
                        }
                    }
                    return min;
                }
            }
            
        }
        return array[start];
    }
}

发表于 2020-05-30 21:34:41 回复(0)

Java

何止hz

只能通过93.3，无语了。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @Date: 2020-05-05 14:35
 * @version: 1.0
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        int num[] = new int[s.length];
        for (int i = 0; i < num.length; i++)
            num[i] = Integer.valueOf(s[i]);
        int l = 0;
        int r = num.length-1;
        int mid;
        while (l<=r){
            mid = (l+r)>>1;
            if (num[mid]>=num[r])
                l=mid+1;
            else
                r = mid;
        }
        System.out.println(num[r]);
    }
}

发表于 2020-05-05 15:04:44 回复(0)

Java

lmz9509

/*
找到第一个元素小于前面的元素，该值为最小
*/

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        //Scanner input = new Scanner(System.in);//会超时
        //String[] str = input.nextLine().split(" ");
        String[] str = input.readLine().split(" ");
        int[] arr = new int[str.length];
        for(int i = 0;i<str.length;i++)
            arr[i] = Integer.parseInt(str[i]);
        
        //
        int result = arr[0];
        for(int i = 0;i<arr.length - 1;i++){
            if(arr[i+1]<arr[i]){
                result = arr[i+1];
                break;
            }
        }
        System.out.println(result);
    }
}

发表于 2020-04-28 14:28:22 回复(0)