文档章节

【九度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
【编程题目】旋转数组的最小数字的高效解法(C++实现)

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

qq_28869927
2017/03/29
0
0
[剑指offer] 旋转数组的最小数字

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

繁著
08/12
0
0
剑指offer 7. 旋转数组的最小数字

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

dby_freedom
10/19
0
0
[算法总结] 13 道题搞定 BAT 面试——字符串

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

繁著
09/05
0
0

没有更多内容

加载失败,请刷新页面

加载更多

设计模式之单例模式

单例模式核心:保证一个类只有一个对象 单例模式分为五种:懒汉式、饿汉式、双重检测锁式、静态内部类式、枚举式 五种模式的特点:懒汉式---线程安全,调用效率高,不能延时加载 饿汉式---线...

森林之下
今天
2
0
markdown语法

这篇博客是本人在使用markdown语法过程中,用于记录一些自己总是会忘记的语法,并且会持续更新; 如何增加批注/备注:>; 这是一条备注/引言 如何手动换行,行末两次空格;

BlackCanary
今天
3
0
redis 设置外网可访问

前提是你已经把redis的端口放到了防火墙计划中,  /sbin/iptables -I INPUT -p tcp --dport 6379 -j ACCEPT /etc/rc.d/init.d/iptables save 更改redis.conf 文件 bind 127.0.0.1prot...

时刻在奔跑
今天
2
0
css3隐藏滚动条

chrome 和Safari .element::-webkit-scrollbar { width: 0 } IE 10+ .element { -ms-overflow-style: none; } Firefox .element { overflow: -moz-scrollbars-none; } firefox这个没试过~啦啦......

呵呵闯
今天
3
0
Poco官方PPT_020-ErrorHandlingAndDebugging双语对照翻译

因工作需要用到这一块的功能,所以直接翻译了一下 此PPT来源于官方文件,地址https://pocoproject.org/documentation.html

CHONGCHEN
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部