olive_lv: 面试题8：旋转数组的最小数字

星期三, 二月 17, 2016

查找：顺序查找、二分查找、哈希表查找和二叉排序树查找。

哈希表主要优点是利用它可在o(1)时间查找某一元素，但缺点是需要额外空间实现哈希表。

与二叉排序树查找对应的数据结构是二叉搜索树。

排序：插入排序、冒泡排序、归并排序、快速排序等算法。

面试题8：旋转数组的最小数字

//题目描述

//把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋

//转，输入一个非递减序列的一个旋转，输出旋转数组的最小元素。例如

//数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1.

#include<vector>

#include<iostream>

using namespace std;

class Solution{

public:

int minNumberInRotateArray(vector<int>rotateArray){

if(rotateArray.size()==0)return 0;

for(int i=0;i<rotateArray.size()-1;i++){

if(rotateArray[i]>rotateArray[i+1])return rotateArray[i+1];

}

return rotateArray[0];

}

};

//int main(){

// vector<int>array=vector<int>();

// array.push_back(1);

// array.push_back(2);

// array.push_back(3);

// array.push_back(4);

// array.push_back(5);

// Solution test=Solution();

// cout<<test.minNumberInRotateArray(array);

// system("pause");

// return 0;

//}

上述算法的时间复杂度为O(n)

旋转之后的数组可以划分为两个排序的子数组，且前面的子数组元素都大于或等于后面的子数组，最小元素刚好是这两个子数组的分界线。可使用二分查找法寻找最小值。

olive_lv