九度OJ-題目1386:回転配列の最小数字

タイトルリンクアドレス:
九度OJ-題目1386:回転配列の最小数字
テーマの説明:1つの配列の最初のいくつかの要素を配列の末尾に運んで、私たちは配列の回転と呼ばれています.増分ソートされた配列の回転を入力し、回転配列の最小要素を出力します.例えば、配列{3,4,5,1,2}は{1,2,3,4,5}の回転であり、この配列の最小値は1である.
入力:入力には複数のテストサンプルが含まれる場合があります.各テストケースについて、入力された最初の動作の整数n(1<=n<=1000000):回転配列を表す要素の数です.入力された2行目はn個の整数を含み、各整数aの範囲は(1<=a<=1億円)である.
出力:各テストケースに対応して、回転配列の最小要素を出力します.
サンプル入力:5 3 4 5 1 2
サンプル出力:1
問題解決の考え方:
題意から分かるように,インクリメンタル配列の回転配列は2つのインクリメンタルサブ配列からなり,2番目のインクリメンタルサブ配列の最初の要素は回転配列の最小数である.そこで私の考えは,回転配列array[0,1,...n−1]を巡回することによって,array[i]#include<stdio.h> #define MAX 1000001 int array[MAX]; /** * ， 2 * @param n * @return min */ int findMinValueInRotateArray(int n) { int i; int min = array[0]; // ， array[0] for(i = 0;i < n - 1;i++) { if(array[i] > array[i + 1]) { min = array[i + 1]; break; } } return min; } int main() { int i,n; int result; while(EOF != scanf("%d",&n)) { for(i = 0;i < n;i++) { scanf("%d",&array[i]); } result = findMinValueInRotateArray(n); printf("%d
",result); } return 0; } /************************************************************** Problem: 1386 User: blueshell Language: C Result: Accepted Time:670 ms Memory:4820 kb ****************************************************************/