MIOJ #14 在一个有序的经过旋转的数组里查找一个数

描述

假设一个有序的数组,经过未知次数的旋转(例如0 1 2 4 5 6 7 被旋转成 4 5 6 7 0 1 2),从中查找一个目标值,如果存在,返回其下标,不存在,返回-1。注:假设数组无重复数字

输入

输入一个有序经过旋转的数组和要查找的目标数字,数组中各数字用“逗号”分隔,数组和目标数字用“空格”分隔

输出

一个整数,表示该目标数字的下标(不存在返回-1)

输入样例

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

输出样例

2

AC代码:

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

int main()
{
    vector<int>a(0);
    int k ;
    int num;
    string s;
    while(cin>>s>>num)
    {
        s = s+",";
        bool flag = false;
        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);
            }
        }
        for(int i = 0;i<a.size();i++){
            if(a[i] == num){
                cout<<i<<endl;
                break;
            }
            if(i == a.size()-1){
                cout<<"-1"<<endl;
            }
        }
    }
}

 

发表回复

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