首页 > 试题广场 > 旋转数组中的最小元素
[编程题]旋转数组中的最小元素
把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个排好序的数组的一个旋转,输出旋转数组的最小元素。例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转,该数组的最小值为1。

输入描述:
一个排好序的数组的一个旋转
数组长度不超过1000000


输出描述:
该数组的最小值
示例1

输入

3 4 5 1 2

输出

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 回复(1)
第一种不太推荐
如果题目有时间复杂度要求或者是测试用例给的数组特别大,这种根本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 回复(1)
#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)
""""
求最小值?
"""

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

发表于 2019-07-14 12:16:04 回复(0)

参考了大佬的解法,二分。

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = 0;
        int[] arr = new int[1000000];
        while(sc.hasNext()) {
            arr[n ++] = sc.nextInt();
        }

        int l = 0;
        int r = n - 1;
        while(l < r) {
            int mid = (l + r) >>> 1;
            if(arr[mid] > arr[r]) {
                l = mid + 1;
            } else if(arr[mid] < arr[r]) {
                r = mid;
            } else {
                r = r - 1;
            }
        }

        System.out.println(arr[l]);
    }
}
编辑于 2019-08-20 11:37:04 回复(0)
# 我的解法:python3 的二分法,参考上面回答的那位同学
if __name__ == "__main__":
    list = list(map(int, input().strip().split()))
   # low和high用于跟踪要在其中查找的列表部分
    low = 0
    high = len(list) - 1
    while low <= high:    # 只要范围没有缩小到只包含一个元素,就检查中间的元素
        mid = (low + high) // 2   # 如果(low + high)不是偶数,Python自动将mid向下取整
        if list[mid] > list[high]: # 当中间元素大于最后一个,表明最小值在右半区间
            low = mid + 1
        elif list[mid] < list[high]:  # 当中间元素小于最后一个,表明最小值在左半区间,注意没有减一操作
            high = mid
        else:                    # 当中间元素等于最后一个,说明没有指定的元素,将范围缩小一
            high = high - 1
    print(list[mid])
总算是通过了测试,之前写的一种方法没通过,它逻辑上是:对于这个排序后的旋转数组list,如果从最小值那个位置i切分,那么恰好同时有list[i] < list[i-1] 和 list[i] < list[i+1]成立
发表于 2019-08-06 15:06:58 回复(2)