文档章节

【九度OJ1386】|【剑指offer8】旋转数组的最小数字

aqia358
 aqia358
发布于 2013/10/17 21:31
字数 377
阅读 34
收藏 0
题目描述:

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

输入:

输入可能包含多个测试样例,对于每个测试案例,

输入的第一行为一个整数n(1<= n<=1000000):代表旋转数组的元素个数。

输入的第二行包括n个整数,其中每个整数a的范围是(1<=a<=10000000)。

输出:

对应每个测试案例,

输出旋转数组中最小的元素。

解:很简单的一道题但提交后前两个总是也不能通过,后来才发现有两种情况需要额外注意一下:

  1. 输入的是全部相同的数
  2. 输入的是没有变换顺序的数组
    即数组的第一位已经是最小的了,再跟后面的比较无法取得更小的数,从而导致错误
    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.io.StreamTokenizer;
    
    /**
     * 旋转数组的最小数字
     * @author aqia358
     *
     */
    public class Main {
    
    	public static void main(String[] args) throws IOException {
    		StreamTokenizer st = new StreamTokenizer(new BufferedReader(
    				new InputStreamReader(System.in)));
    		while (st.nextToken() != st.TT_EOF) {
    			int n = (int) st.nval;
    			int count = 0;
    			int[] a = new int[n];
    			boolean flag = false;
    				while (count < n) {
    					st.nextToken();
    					a[count] = (int) st.nval;
    					if (count >= 1) {
    						if (a[count] < a[count - 1]) {
    							flag = true;
    							System.out.println(a[count]);
    						}
    					}
    					count++;
    				}
    				if(!flag)
    					System.out.println(a[0]);
    		}
    	}
    
    }


© 著作权归作者所有

共有 人打赏支持
aqia358
粉丝 6
博文 82
码字总数 30297
作品 0
海淀
程序员
剑指Offer学习总结-旋转数组的最小数字

剑指Offer学习总结-旋转数组的最小数字 本系列为剑指Offer学习总结,主要是代码案例的分析和实现: 书籍链接:http://product.dangdang.com/24242724.html 原作者博客:http://zhedahht.blo...

wwlcsdn000
01/16
0
0
[剑指offer] 旋转数组的最小数字

本文首发于我的个人博客:尾尾部落 题目描述 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{...

繁著
08/12
0
0
【编程题目】旋转数组的最小数字的高效解法(C++实现)

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

qq_28869927
2017/03/29
0
0
[算法总结] 13 道题搞定 BAT 面试——字符串

本文首发于我的个人博客:尾尾部落 1. KMP 算法 谈到字符串问题,不得不提的就是 KMP 算法,它是用来解决字符串查找的问题,可以在一个字符串(S)中查找一个子串(W)出现的位置。KMP 算法把...

繁著
09/05
0
0
算法知识梳理(4) - 数组第一部分

面试算法代码知识梳理系列 算法知识梳理(1) - 排序算法 算法知识梳理(2) - 字符串算法第一部分 算法知识梳理(3) - 字符串算法第二部分 算法知识梳理(4) - 数组第一部分 一、概要 本文介绍了有...

泽毛
2017/11/10
0
0

没有更多内容

加载失败,请刷新页面

加载更多

OSChina 周四乱弹 —— 毒蛇当辣条

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @ 达尔文:分享花澤香菜/前野智昭/小野大輔/井上喜久子的单曲《ミッション! 健?康?第?イチ》 《ミッション! 健?康?第?イチ》- 花澤香菜/前野智...

小小编辑
45分钟前
4
0
java -jar运行内存设置

java -Xms64m #JVM启动时的初始堆大小 -Xmx128m #最大堆大小 -Xmn64m #年轻代的大小,其余的空间是老年代 -XX:MaxMetaspaceSize=128m # -XX:CompressedClassSpaceSize=6...

李玉长
55分钟前
1
0
Spring | 手把手教你SSM最优雅的整合方式

HEY 本节主要内容为:基于Spring从0到1搭建一个web工程,适合初学者,Java初级开发者。欢迎与我交流。 MODULE 新建一个Maven工程。 不论你是什么工具,选这个就可以了,然后next,直至finis...

冯文议
今天
1
0
RxJS的另外四种实现方式(四)——性能最高的库(续)

接上一篇RxJS的另外四种实现方式(三)——性能最高的库 上一篇文章我展示了这个最高性能库的实现方法。下面我介绍一下这个性能提升的秘密。 首先,为了弄清楚Most库究竟为何如此快,我必须借...

一个灰
今天
1
0
麒麟AI首席科学家现世

8月31日,华为发布了新一代顶级人工智能手机芯片麒麟980,成为全球首款7nm工艺手机芯片,AI方面也实现飞跃,支持人脸识别、物体识别、物体检测、图像分割、智能翻译等。 虽然如今人人都在热议...

问题终结者
昨天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部