题目:把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如:
数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为。
解题思路:就是变形的二分查找,但是要考虑特殊情况,例如{1,0,1,1,1},此时只能采取顺序查找。
#include<iostream> using namespace std; // int findMinNum1(int tempArray[], int count){ int tempMinNum = tempArray[0]; for(int i = 1; i < count; i++){ tempMinNum = (tempMinNum < tempArray[i]) ? tempMinNum : tempArray[i]; } return tempMinNum; } // int findMinNum(int tempArray[], int count){ int i = 0; int j = count - 1; while(j - i > 1){ int m = (i + j)/2; if(tempArray[i] > tempArray[m]){ j = m; }else if(tempArray[j] < tempArray[m]){ i = m; }else{ // 出现重复数字,需要顺序遍历查找 return findMinNum1(tempArray, count); } } return tempArray[j]; } int main(){ // int tempArray[8] = {1,2,3,4,5,6,7,0}; int tempArray[9] = {1,0,0,1,1,1,1,1,1}; cout<<"数组中的最小元素为 "<<findMinNum(tempArray, 9)<<endl; system("pause"); return 0; }