剑指offer:旋转数组的最小数字

时间:2022-09-10 09:49:22

题目描述:

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{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:旋转数组的最小数字的更多相关文章

  1. 剑指Offer 旋转数组的最小数字

    题目描述 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转.输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素.例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转 ...

  2. 剑指Offer——旋转数组的最小数字

    题目描述: 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转. 输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素. 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一 ...

  3. 用js刷剑指offer&lpar;旋转数组的最小数字&rpar;

    题目描述 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转. 输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素. 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个 ...

  4. 剑指Offer&lowbar;11&lowbar;旋转数组的最小数字

    题目描述 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转.输入一个递增排序的数组的一个旋转,输出一个旋转数组的最小元素. 例如: {3,4,5,1,2} 为 {1,2,3,4,5} ...

  5. 剑指offer-7&period;旋转数组的最小数字

    看起来不需要用二分法查找 --------------------------------------------------------- 时间限制:3秒 空间限制:32768K 热度指数:5098 ...

  6. 剑指Offer-6&period;旋转数组的最小数字&lpar;C&plus;&plus;&sol;Java&rpar;

    题目: 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转.输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素.例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转, ...

  7. 剑指offer6&colon;旋转数组的最小数字

    1. 题目描述 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转.输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素.例如数组{3,4,5,1,2}为{1,2,3,4,5}的一 ...

  8. 剑指offer8 旋转数组的最小数字

    一种错误写法: class Solution { public: int minNumberInRotateArray(vector<int> rotateArray) { int len ...

  9. 剑指offer-旋转数组的最小数字06

    题目描述 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转. 输入一个非减排序的数组的一个旋转,输出旋转数组的最小元素. 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋 ...

  10. 剑指offer-旋转数组的最小数字-数组-python

    题目描述 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转.输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素.例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转 ...

随机推荐

  1. 如何安装并简单的使用OwinHost——Katana

    微软OWIN的提出必然会引起一场风暴,而我们作为C#阵营中一份子,自然免不了会卷入其中.OWIN是什么东西,我在这里就不解析了,还不知道是OWIN是什么的读者请打开浏览器,然后搜索即可,中文的英文的应 ...

  2. JS高级程序设计&&num;160&semi;笔记

    1.instanceof 可以判断实例是否在某个对象的原型上: function A() { this.a = "a"; } function B() { this.b = &qu ...

  3. 关于 CAS 不能登录的问题

    经过排查,是因为 Capistrano 部署中设置了 http_proxy.此时通过 cas.m.xxxx.com 域名去访问 CAS 服务时,就不通了,需要修改为 IP 来访问. 但是公司的 CAS ...

  4. 收缩SQL数据库日志文件

    收缩SQL数据库日志文件 介绍具体的操作方法前,先说下我操作的实际环境和当时的状况.我的服务器是windows server 2008 R2 64位英文版,数据库是SQL server 2008英文版 ...

  5. C&num; Log4Net配置

    Log4Net是用来记录日志的,可以将程序运行过程中的信息输出到一些地方(文件.数据库.EventLog等),日志就是程序的黑匣子,可以通过日志查看系统的运行过程,从而发现系统的问题.日志的作用:将运 ...

  6. HDOJ 1163 Eddy&&num;39&semi;s digital Roots 九余数定理&plus;简单数论

    我在网上看了一些大牛的题解,有些知识点不是太清楚, 因此再次整理了一下. 转载链接: http://blog.csdn.net/iamskying/article/details/4738838 ht ...

  7. Linux下 输入 env 而得到的环境变量解读

    HOSTNAME=Master.Hadoop MAHOUT_HOME=/usr/hadoop/mahout-distribution-0.8 TERM=linux SHELL=/bin/bash HA ...

  8. 海量数据处理 - 10亿个数中找出最大的10000个数(top K问题)

    前两天面试3面学长问我的这个问题(想说TEG的3个面试学长都是好和蔼,希望能完成最后一面,各方面原因造成我无比想去鹅场的心已经按捺不住了),这个问题还是建立最小堆比较好一些. 先拿10000个数建堆, ...

  9. tcp config

    $ sudo sysctl net.ipv4.tcp_reordering=1 $ sudo sysctl net.ipv4.tcp_thin_linear_timeouts=1 $ sudo sys ...

  10. ASCII&comma;unicode&comma; utf8 &comma;big5 &comma;gb2312&comma;gbk&comma;gb18030等几种常用编码区别(转载)

    原文出处:http://www.blogjava.net/xcp/archive/2009/10/29/coding2.html 最近老为编码问题而烦燥,下定决心一定要将其弄明白!本文主要总结网上一些 ...