MIOJ #5 找出旋转有序数列的中间值

描述

给出一个有序数列随机旋转之后的数列,如原有序数列为:[0,1,2,4,5,6,7] ,旋转之后为[4,5,6,7,0,1,2]。 假定数列中无重复元素,且数列长度为奇数。 求出旋转数列的中间值。如数列[4,5,6,7,0,1,2]的中间值为4。

输入

4,5,6,7,0,1,2

输出

4

输入样例

1
1,2,3
4,5,6,7,0,1,2
12,13,14,5,6,7,8,9,10

输出样例

1
2
4
9

AC代码:

#include <bits/stdc++.h>
#include<vector>
using namespace std;

int main()
{
    string s;

    while(cin>>s)
    {
        s = s+",";
        bool flag = false;
        vector<int>a(0);
        int b = 0;
        int j = 0;
        int k = 0;
        int cnt = 0;
        int temp = -1;
        for(int i = 0; i<s.length(); i++)
        {
            flag = false;
            b = 0;
            k = j;
            if(s[i] ==',')
            {
                while(k != i)
                {
                    b = b*10+(s[k]-48);
                    k++;
                }
                flag = true;
                // cout<<b<<endl;
                j = i+1;
            }
            if(flag == true)
            {
                a.push_back(b);
            }
        }
        temp = -1;
        for(int i = 0;i<a.size()-1;i++){
            if(a[i] > a[i+1]){
                temp = i;
            }
        }
        if(temp == -1){
            cout<<a[a.size()/2]<<endl;
        }
        else if(temp >= a.size()/2){
            cout<<a[a.size()/2-temp]<<endl;
        }
        else if(temp < a.size()/2){
            cout<<a[a.size()/2+temp+1]<<endl;
        }
    }
}

 

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注