首页 > 试题广场 >

旋转数组中的最小元素

[编程题]旋转数组中的最小元素
  • 热度指数：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

输出

1
算法知识视频讲解
添加回答
Python
ElonB头像 ElonB 
""""
求最小值？
"""

if __name__ == "__main__":
    a = list(map(int, input().strip().split()))
    print(min(a))

发表于 2019-07-14 12:16:04 回复(3)
C/C++
昔遥暮云头像 昔遥暮云 
#include <bits/stdc++.h>
using namespace std;
int main(){
    int mi=INT_MAX,t;
    while(1){
        cin>>t;
        mi=min(mi,t);
        if(cin.get()=='\n')
            break;
    }
    cout<<mi;
    return 0;
}

编辑于 2019-11-13 19:31:51 回复(0)
藤和艾莉欧。头像 藤和艾莉欧。 
第一种不太推荐
如果题目有时间复杂度要求或者是测试用例给的数组特别大，这种根本AC不了的
#include<bits/stdc++.h>
using namespace std;
int main(){
        vector<int>num;
        int n;
        while(cin>>n)
            num.push_back(n);
        if(num.size() == 0)
            return 0;
        sort(num.begin(),num.end());   
        cout<<num[0]<<endl;
        return 0;
}
第二种是采取二分法
看到有序就应该想到二分法的（前后两个小数组分别是非递减数组，注意是非递减）
#include<bits/stdc++.h>
using namespace std;
int main(){
   vector<int>num;
   int n;
   while(cin>>n)
       num.push_back(n);
   int left=0,right=num.size()-1;
   while(left<right) {
        int mid=(left+right)>>1;
        if(num[mid]>num[right])
             left=mid+1;//当中间元素大于最后一个，表明最小值在右半区间                
        else if(num[mid]<num[right])
             right=mid;//当中间元素小于最后一个，表明最小值在左半区间，注意没有减一操作
        else right=right-1;//当中间元素 等于 最后一个，例如 2341001说明有重复元素，将范围缩小一个        }
   cout<<num[left]<<endl;
   return 0;
}

  

编辑于 2019-08-06 10:18:16 回复(5)
C/C++
邂逅龙头像 邂逅龙
十分取巧，卑微~ 
#include<bits/stdc++.h>
using namespace std;
int main()
{
	set<int> s;
	int x;
	while(cin>>x)
	{
		s.insert(x);	
	}
	set<int>::iterator it=s.begin();
	cout<<*it<<endl;
	return 0;	
} 


发表于 2020-08-31 15:24:42 回复(0)
给我offer我要offer头像 给我offer我要offer 
import java.util.*;
import java.io.*;
public class Main{
    public static int func(int[] arr){
        int min=arr[0];
        for(int i=1;i<arr.length;i++){
            if(arr[i]<min){
                min=arr[i];
            }
        }
        return min;
    }
    public static void main(String[] args) throws IOException{
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        //Scanner sc=new Scanner(System.in);
        String[] nums=input.readLine().split(" ");
        int num[]=new int[nums.length];
        for(int i=0;i<num.length;i++){
            num[i]=Integer.valueOf(nums[i]);
        }
        System.out.println(func(num));
    }
}

发表于 2020-08-27 19:39:58 回复(0)
C/C++
广州市民林先生头像 广州市民林先生
旋转数组之后，分为两部分，从左到右都是非递减的，既然是有序数组，我们一般考虑用二分法，这个题是二分的变种，存在2个区间（左、右），并且左区间最小值（第一个数）肯定大于等于右区间最小值（第一个数）以及其后面的所有数，也就是大于右区间所有值，所以当第一次出现arr[左] < arr[右]的时候，即出现了最小值。代码如下 
#include <iostream>
#include <vector>
using namespace std;

int main(){
    vector<int> vec;
    int val;
    while(cin >> val){
        vec.push_back(val);
    }
    //有序数组 - 二分
    int low = 0;
    int high = vec.size() - 1;
    while(low < high){
        // 1 2 3 4 5 -> 3 4 5 1 2
        if(vec[low] < vec[high]){
            //第一次出现vec[low]<vec[high]即出现最小值
            cout << vec[low] << endl;
            return 0;
        }
        int mid = low + (high - low)/2;
        //确定左、右部分的增减区间
        if(vec[low] < vec[mid]){  //左区间是非递减的
            low = mid + 1;  
        }
        else if(vec[high] > vec[mid]){ //右区间也是非递减的
            high = mid;
        }
        else{
            ++low;
        }
    }
    cout << vec[low] << endl;  //不要忘了这步，22222/22212这种类型
    return 0;
}


编辑于 2020-06-03 22:07:58 回复(0)
Java
lmz9509头像 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)
牛客Cver头像 牛客Cver
请问大家的代码是如何通过的呀？为什么我的程序代码一直没有输出呢？是因为我还不会使用这个自带的编译器还是什么原因？真心地求指教！！！！😔 

class Solution:
    def findMinForRaNum(self,nums):
        if len(nums) == 1:
            return nums[0]
        
        l, h = 0, len(nums)-1
        
        while l < h:
            mid = int(l + (h - l)/2)
            if nums[mid] > nums[h]:
                l = mid + 1
            else:
                h = mid
        return nums[l]
    
while True:
    try:
        nums = list(map(int, raw_input().split()))
        s = Solution()
        result = s.findMinForRaNum(nums)
        print(result)
    except:
        break


发表于 2020-03-11 21:10:45 回复(1)
路人罢了头像 路人罢了
这题就挺离谱的。相同代码，Arrays.sort(a),使用BufferedReader过了，使用Scanner过不了。
使用 Scanner +二分法。取值时候
 String str=in.nextLine(); String []s=str.split(" ")；这种过不了
使用int[] a = new int[1000000];
        while(in.hasNext()) {
            a[n++] = in.nextInt();
        }
又过了。
总的就是就你妈离谱。还不如直接一开始就保存最小值。排个锤子的序。 
/*import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main{
    public static void main(String args[])throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String str=in.readLine();
        String []s=str.split(" ");
        int []a=new int[s.length];
        for(int i=0;i<s.length;i++){
            a[i]=Integer.parseInt(s[i]);
        }
        Arrays.sort(a);
        System.out.println(a[0]);
    }
}*/
import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner in=new Scanner(System.in);  
        int n = 0;
        int[] a = new int[1000000];
        while(in.hasNext()) {
            a[n++] = in.nextInt();
        }
            int l=0;
            int r=n-1;
            while(r>l){
                int mid=(l+r)/2;
                if(a[mid]<a[r])r=mid;
                else if(a[mid]>a[r])l=mid+1;
                else {
                    r = r - 1;
                }
            }  
            System.out.println(a[l]);
    }
}


发表于 2020-02-10 04:11:50 回复(1)
字节跳动校招社招内推头像 字节跳动校招社招内推 
import java.util.*;
public class Main{
    public static void main(String []args){
    	fun81812();
    }
    public static void fun81812()
    {
    	Scanner in=new Scanner(System.in);
        int min=in.nextInt();
        while(in.hasNext())
        {
            int now=in.nextInt();
            if(now<min)
            {
                min=now;
            }
        }
        System.out.println(min);
    	/*String []k=in.nextLine().split(" ");
        int min=Integer.parseInt(k[0]);
        for(int i=0;i<k.length;i++)
        {
            int now =Integer.parseInt(k[i]);
            if(now<min)
            {
                min=now;
            }
        }
        System.out.println(min);*/
    }
}
被自己蠢到的一道题，因为反正要读取输入啊，直接每次都比较保存了最小值不就好了？被描述带偏了也是第一次。下次注意额

发表于 2019-08-18 23:37:38 回复(2)
C/C++
nbgao头像 nbgao 
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n=0, x, Min = INT_MAX;
    while(cin>>x){
        Min = min(Min, x);
    }
    cout<<Min<<endl;
    return 0;
}

发表于 2019-07-19 10:24:36 回复(0)
C/C++
牛客549207409号头像 牛客549207409号
#include<iostream>
#include<vector>
#include<algorithm>
int main()
{
    int n;
    std::vector<int>s;
    while(std::cin>>n)s.push_back(n);
    sort(s.begin(),s.end());
    std::cout<<s[0]<<std::endl;
    return 0;
}
发表于 2020-09-20 23:41:37 回复(0)
Python
138182590头像 138182590 
def getMin(arr):
    low = 0
    high = len(arr) - 1
    if len(arr) == 0:
        return 0
    if len(arr) ==1:
        return arr[0]
    while low <= high:
        mid = (low + high) >> 1 # 右移一位相当于除以2
        if arr[mid]>arr[high]:
            low = mid + 1
        elif arr[mid] < arr[low]:
            high = mid
        else:
            high -= 1
    return arr[low]

发表于 2020-09-14 17:23:18 回复(1)
weiYyx头像 weiYyx 
#l = list(map(int, input().split()))
#print(min(l))

class Solution:
    def minArray(self, numbers):
        for i in range(len(numbers)-1):
            if numbers[i] > numbers[i+1]:
                return numbers[i+1]
        return numbers[0]
while True:
    try:
        numbers = list(map(int, input().split()))
        s = Solution()
        result = s.minArray(numbers)
        print(result)
    except:
        break

发表于 2020-09-08 16:28:42 回复(0)
Java
牛客886618438号头像 牛客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头像 何止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)
PandaLai头像 PandaLai
请教一下大家，下面这段代码卡在了93.3%的位置，卡的测试用例是2047个2，但是想不明白为什么会被卡（输出只提示说没有通过所有的测试用例，没有指明具体原因，也看不到程序的真实输出）。把代码第11行改成 if nums[low] < nums[high]: 以后就全过了。本地测试的时候，两个版本对于卡的测试用例又都能输出正确答案，感觉很玄学。求大佬解答。 
import sys

def solve(nums):
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]
    low, high = 0, len(nums)-1
    while low < high - 1:
        mid = (low + high) // 2
        if nums[low] < nums[mid] < nums[high]:
            return nums[low]
        if nums[mid] > nums[low]:
            low = mid + 1
        elif nums[mid] < nums[low]:
            high = mid
        else:
            low += 1
    return min(nums[low], nums[high])

nums = map(int, sys.stdin.readline().strip().split())
print solve(nums)


发表于 2020-03-28 21:36:48 回复(5)
吧啦吧啦蹦跶头像 吧啦吧啦蹦跶
python2.7通过
while True:
    try:
        d = list(map(int, raw_input().split()))
        m = min(d)
        print m
    except:
        break
发表于 2020-01-15 17:23:46 回复(0)
牛客282965463头像 牛客282965463 
#include <iostream>
#include <vector>

using namespace std;
void rotateArrayMin(vector<int>& vec)
{
    int l = 0;
    int r = vec.size()-1;
    int mid;
    while(l < r)
    {
        mid = l + (r-l)/2;
        if(vec[mid] == vec[r])
        {
            --r;
        }
        else if(vec[mid] < vec[r])
        {
            r = mid;
        }
        //直接写成else l = mid + 1即可，多了左边的比较，效率也变低，比较蠢
        else if(vec[mid] > vec[l])
        {
            l = mid + 1;
        }
        else if(vec[mid] == vec[l])
        {
            l = l + 1;
        }
            
    }
    cout << vec[l] << endl;
}
int main()
{
    vector<int> vec;
    int n;
    while(cin >> n)
        vec.push_back(n);
    rotateArrayMin(vec);
    return 0;
}

编辑于 2019-11-13 09:56:48 回复(0)
热心市民刘先生201908241440517头像 热心市民刘先生201908241440517 
def minValueRotateArray(rotateArray):
    
    if rotateArray == []:
        return 0
    left=0
    right = len(rotateArray)-1
    while left != right and left != right-1:
        if rotateArray[left] > rotateArray[right]:
            temp = int((left+right)/2)
            if rotateArray[temp] >= rotateArray[left]:
                left = temp
            else :
                right = temp
        elif rotateArray[left] == rotateArray[right]:
            temp = right-1
            if rotateArray[temp] > rotateArray[left]:
                left = temp
            else :
                right = temp
        else :
            temp = int((left+right)/2)
            if rotateArray[temp] > rotateArray[left]:
                right = temp
            else :
                left = temp
    if rotateArray[left] > rotateArray[right]:
        return rotateArray[right]
    else :
        return rotateArray[left]

if __name__ == '__main__':
    listx = input()
    listy = []
    for ix in listx.split(' '):
        listy.append(int(ix))
    minValue = minValueRotateArray(listy)
    print(minValue)

题说排序，第一个注意点，非递增还是非递减
查找最小值，常用的是遍历，但比较费时，如果是重复元素较多的那只能是一个个遍历啦比如3333033
当然，该题使用二分法比较便捷。
如非递增：
第一个元素小于等于最后一个元素，这是必须的
而非递减：
第一个元素大于等于最后一个元素，因此等于这个情况只能通尾下标递减或者首下标递增的方式来遍历
而对于大于或者小于，那就直接使用二分法来解决啦
发表于 2019-09-06 10:23:08 回复(0)
提交观点

问题信息

C++工程师 数组 小米集团 测试开发工程师 测试工程师 2019 查找 排序 Java工程师
来自：小米2019秋招测试开...
上传者：小小
难度：
22条回答 8597浏览

热门推荐

通过挑战的用户

查看代码

相关试题

旋转数组中的最小元素

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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