题目描述:
把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。
解题思路:
最直观的想法就是遍历一遍数组,找到最小值,但这样明显没有用到旋转数组这个信息。
由于这个旋转的操作实际上是将原数组划分成了两个有序的数组,第一个数组是大于第二个数组的,所以考虑用二分的思想。设定两个指针,指针p1指向第一个递增数组,指针p2指向第二个递增数组,两个指针的中间值mid和对应两个指针所指向的值对比,若mid比p1所值元素大,则说明最小元素在后半段,此时p1移动到mid位置,数组长度减半;若mid比p2所值元素小,则说明最小元素在前半段,此时p2移到mid位置。这样到最后,p1和p2就相临,其中p1指向第一个递增数组的最后一位,p2指向第二个递增数组的第一位,即最小值为p2所值元素。
需要注意以下两个特殊情况:
1. 若原数组没有旋转,那么第一个元素即为最小值;
2. 若左右指针所指元素和中间元素都相等,此时就无法决定指针要如何移动,即无法确定最小元素在前半段还是后半段。此时只能通过顺序查找最小元素。
时间复杂度为O(logn),最坏情况下为O(n)。
代码:
class Solution {
public:
int minNumberInRotateArray(vector<int> rotateArray)
{
if(rotateArray.empty())
{
return ;
}
int left=;
int right=rotateArray.size()-;
if(rotateArray[left]<rotateArray[right])
{
return rotateArray[left];
}
int mid = left;
while(right>left)
{
mid=(right+left)/;
int middle=rotateArray[mid];
int leftNumber=rotateArray[left];
int rightNumber=rotateArray[right];
if((right-left)==)
{
return rightNumber;
}
//左中右的值全都相等,不能确定在前还是在后,只能遍历查后一个比前一个小就是最小值
if(middle==leftNumber&&middle==rightNumber)
{
for(int i=left;i<right;i++)
{
if(rotateArray[i]>rotateArray[i+])
{
return rotateArray[i+];
}
}
//全相等的话直接返回最左值就行了
return leftNumber;
}
else if(middle<leftNumber)
{
right=mid;
}
else if(middle>rightNumber)
{
left=mid;
}
}
return rotateArray[mid];
}
};
剑指offer:旋转数组的最小数字的更多相关文章
-
剑指Offer 旋转数组的最小数字
题目描述 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转.输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素.例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转 ...
-
剑指Offer——旋转数组的最小数字
题目描述: 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转. 输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素. 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一 ...
-
用js刷剑指offer(旋转数组的最小数字)
题目描述 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转. 输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素. 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个 ...
-
剑指Offer_11_旋转数组的最小数字
题目描述 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转.输入一个递增排序的数组的一个旋转,输出一个旋转数组的最小元素. 例如: {3,4,5,1,2} 为 {1,2,3,4,5} ...
-
剑指offer-7.旋转数组的最小数字
看起来不需要用二分法查找 --------------------------------------------------------- 时间限制:3秒 空间限制:32768K 热度指数:5098 ...
-
剑指Offer-6.旋转数组的最小数字(C++/Java)
题目: 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转.输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素.例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转, ...
-
剑指offer6:旋转数组的最小数字
1. 题目描述 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转.输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素.例如数组{3,4,5,1,2}为{1,2,3,4,5}的一 ...
-
剑指offer8 旋转数组的最小数字
一种错误写法: class Solution { public: int minNumberInRotateArray(vector<int> rotateArray) { int len ...
-
剑指offer-旋转数组的最小数字06
题目描述 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转. 输入一个非减排序的数组的一个旋转,输出旋转数组的最小元素. 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋 ...
-
剑指offer-旋转数组的最小数字-数组-python
题目描述 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转.输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素.例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转 ...
随机推荐
-
如何安装并简单的使用OwinHost——Katana
微软OWIN的提出必然会引起一场风暴,而我们作为C#阵营中一份子,自然免不了会卷入其中.OWIN是什么东西,我在这里就不解析了,还不知道是OWIN是什么的读者请打开浏览器,然后搜索即可,中文的英文的应 ...
-
JS高级程序设计&#160;笔记
1.instanceof 可以判断实例是否在某个对象的原型上: function A() { this.a = "a"; } function B() { this.b = &qu ...
-
关于 CAS 不能登录的问题
经过排查,是因为 Capistrano 部署中设置了 http_proxy.此时通过 cas.m.xxxx.com 域名去访问 CAS 服务时,就不通了,需要修改为 IP 来访问. 但是公司的 CAS ...
-
收缩SQL数据库日志文件
收缩SQL数据库日志文件 介绍具体的操作方法前,先说下我操作的实际环境和当时的状况.我的服务器是windows server 2008 R2 64位英文版,数据库是SQL server 2008英文版 ...
-
C# Log4Net配置
Log4Net是用来记录日志的,可以将程序运行过程中的信息输出到一些地方(文件.数据库.EventLog等),日志就是程序的黑匣子,可以通过日志查看系统的运行过程,从而发现系统的问题.日志的作用:将运 ...
-
HDOJ 1163 Eddy&#39;s digital Roots 九余数定理+简单数论
我在网上看了一些大牛的题解,有些知识点不是太清楚, 因此再次整理了一下. 转载链接: http://blog.csdn.net/iamskying/article/details/4738838 ht ...
-
Linux下 输入 env 而得到的环境变量解读
HOSTNAME=Master.Hadoop MAHOUT_HOME=/usr/hadoop/mahout-distribution-0.8 TERM=linux SHELL=/bin/bash HA ...
-
海量数据处理 - 10亿个数中找出最大的10000个数(top K问题)
前两天面试3面学长问我的这个问题(想说TEG的3个面试学长都是好和蔼,希望能完成最后一面,各方面原因造成我无比想去鹅场的心已经按捺不住了),这个问题还是建立最小堆比较好一些. 先拿10000个数建堆, ...
-
tcp config
$ sudo sysctl net.ipv4.tcp_reordering=1 $ sudo sysctl net.ipv4.tcp_thin_linear_timeouts=1 $ sudo sys ...
-
ASCII,unicode, utf8 ,big5 ,gb2312,gbk,gb18030等几种常用编码区别(转载)
原文出处:http://www.blogjava.net/xcp/archive/2009/10/29/coding2.html 最近老为编码问题而烦燥,下定决心一定要将其弄明白!本文主要总结网上一些 ...