文档章节

面试题8—求“旋转数组”的最小数字

U_C
 U_C
发布于 2014/08/28 20:54
字数 447
阅读 33
收藏 0

旋转数组:把一个数组最开始的若干个数字搬到数组的末尾,我们称之为数组的旋转;例如:{3,4,5,1,2}为{1,2,3,4,5}的一个旋转

解题思路:旋转的数组可以看成是两个排好序的子数组,且前面的子数组大于或者等于后面的子数组,最小的元素是两个数组的分界线;(利用二分查找法一样)

(第一步):用两个指针分别指向数组的第一个元素和最后一个元素

(第二步):找到数组的中间元素,如果该数组位于前面的递增数组,那么它应该大于或者等于第一个指针指向的元素,此时该最小的元素应该位于该中间元素的后面

(第三步):把第一个指针指向该中间元素,以这种方式缩小查找范围

(第四步):找到数组的中间元素,如果该数组位于后面的递增数组,那么它应该小于或者等于第二个指针指向的元素,此时该最小的元素应该位于该中间元素的前面

(第五步):把第二个指针指向该中间元素,以这种方式缩小查找范围

int Min(int *numbers,int length)
{
    if(numbers=NULL||length<=0)
    throw new std::exception("Invalid parameters");
    
    int index1=0,index2=length-1;
    int indexMid=index1;
    while(numbers[index1]>=numbers[index2])
    {
    
    if(index2-index1==1)
    {
            indexMid=index2;
            break; 
    }
    
    indexMid=(index1+index2)/2;
    if(numbers[index1]==numbers[indexMid]&&numbers[index1]==numbers[index2])
            return MinInOrder(numbers,index1,index2);
    if(numbers[indexMid]>=numbers[index1])
          index1=indexMid;
    if(numbers[indexMid]<=numbers[index1])
                 index2=indexMid;
    
    
    }
    
    return numbers[indexMid];




}


//依顺序查找
int MinInOrder(int *numbers,int index1,int index2)
{

    int result=numbers[index1];
    for(int i=index+1;i<=index2;i++)
    {
    
    if(result>numbers[i])
    result=numbers[i];
   
    }
    
    return result;


}

 

 

 

 

© 著作权归作者所有

U_C

U_C

粉丝 0
博文 36
码字总数 16044
作品 0
深圳
私信 提问
编程题——1~10

一、CMyString类的实现(主要是构造函数、拷贝构造函数、赋值运算符、异常安全性) 二、Singleton的实现 1、ns3里的实现 实现程序如下: 2、《C++设计新思维》第6章 多线程实现程序如下: 三...

thanatos_y
2016/07/19
6
0
微软等公司数据结构+算法面试100题

1.把二元查找树转变成排序的双向链表(树) 题目: 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点,只调整指针的指向。 10 / / 6 14 / / / / 4 ...

chambai
2012/08/05
0
0
Android 面试文档分享

一、概述 最近在准备面试的东西,整理了一些读书笔记分享给各位 百度网盘地址,大家可以自由下载,以下内容完全原创。 前两部分是对于一些 经典书籍的读书笔记 和 面试题,都是上学看书的时候...

泽毛
2017/11/10
0
0
面试:谁说的无序就不能用二分查找?

在算法面试中,面试官总是喜欢围绕链表、排序、二叉树、二分查找来做文章,而大多数人都可以跟着专业的书籍来做到倒背如流。而面试官并不希望招收的是一位记忆功底很好,但不会活学活用的程序...

nanchen2251
2018/07/05
0
0
面试:Java 实现查找旋转数组的最小数字

在算法面试中,面试官总是喜欢围绕链表、排序、二叉树、二分查找来做文章,而大多数人都可以跟着专业的书籍来做到倒背如流。而面试官并不希望招收的是一位记忆功底很好,但不会活学活用的程序...

nanchen2251
2018/07/03
0
0

没有更多内容

加载失败,请刷新页面

加载更多

MySQL左连接问题,右表做筛选,左表列依然在

两张表,一张user表,一张user_log表 CREATE TABLE `user` ( `id` int(11) NOT NULL AUTO_INCREMENT, `name` varchar(20) DEFAULT NULL, PRIMARY KEY (`id`)) ENGINE=InnoDB DEFA......

bengozhong
7分钟前
2
0
重新开始学Java——多线程基础

多线程 进程 主流计算机操作系统都支持同时运行多个任务 , 每个任务通常就是一个程序 , 每个运行中的程序就是一个进程或者多个进程 。 进程的特点 独立性 进程是系统中独立存在的实体 可以...

大家都是低调来的
7分钟前
1
0
注解在Java中是如何工作的?

> 来一点咖啡,准备好进入注解的世界。 注解一直是 Java 的一个非常重要的部分,它从 J2SE 5.0 开始就已经存在了。在我们的应用程序代码中,经常看到 @Override 和 @Deprecated 这样的注解。...

liululee
10分钟前
3
0
Docker 容器连接

Docker 容器连接 容器间的链接有两种方法,你选择其一即可 网络端口映射 docker run -d -P docker run -d -p-P :是容器内部端口随机映射到主机的高端口。-p : 是容器内部端口绑定到指定...

测者陈磊
13分钟前
2
0
车载导航应用中基于Sketch UI主题定制方案的实现

1.导读 关于应用的主题定制,相信大家或多或少都有接触,基本上,实现思路可以分为两类: 内置主题(应用内自定义style) 外部加载方式(资源apk形式、压缩资源、插件等) 其实,针对不同的主题...

阿里云官方博客
18分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部