首页 > 试题广场 > 旋转数组中的最小元素
[编程题]旋转数组中的最小元素
  • 热度指数:3270 时间限制: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
第一种不太推荐
如果题目有时间复杂度要求或者是测试用例给的数组特别大,这种根本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 回复(2)
""""
求最小值?
"""

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

发表于 2019-07-14 12:16:04 回复(0)
#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)
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)
#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)
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)
#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)
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)

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

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)