文档章节

【九度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
2018/01/16
0
0
【剑指offer纪念版】-- 面试题目录

2.实现Singleton模式 3.二维数组中的查找 4.替换空格 5.从尾到头打印链表 6.重建二叉树 7.用两个栈实现队列 8.旋转数组的最小数字 9.斐波那契数列 【剑指offer纪念版】--9 斐波那契数列 10.二...

细节探索者
01/19
0
0
[剑指offer] 旋转数组的最小数字

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

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

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

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

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

dby_freedom
2018/10/19
0
0

没有更多内容

加载失败,请刷新页面

加载更多

centos7重置密码、单用户模式、救援模式、ls命令、chmod命令

在工作当中如果我们错误的配置了文件使服务器不能正常启动或者忘记密码不能登录系统,如何解决这些问题呢?重装系统是可以实现的,但是往往不能轻易重装系统的,下面用忘记密码作为例子讲解如...

李超小牛子
今天
3
0
Python如何开发桌面应用程序?Python基础教程,第十三讲,图形界面

当使用桌面应用程序的时候,有没有那么一瞬间,想学习一下桌面应用程序开发?行业内专业的桌面应用程序开发一般是C++,C#来做,Java开发的也有,但是比较少。本节课会介绍Python的GUI(图形用...

程序员补给栈
今天
5
0
kafka在的使用

一、基本概念 介绍 Kafka是一个分布式的、可分区的、可复制的消息系统。它提供了普通消息系统的功能,但具有自己独特的设计。 这个独特的设计是什么样的呢? 首先让我们看几个基本的消息系统...

狼王黄师傅
今天
3
0
Android JNI总结

0x01 JNI介绍 JNI是Java Native Interface的缩写,JNI不是Android专有的东西,它是从Java继承而来,但是在Android中,JNI的作用和重要性大大增强。 JNI在Android中起着连接Java和C/C++层的作...

天王盖地虎626
昨天
3
0
大数据教程(11.8)Hive1.2.2简介&初体验

上一篇文章分析了Hive1.2.2的安装,本节博主将分享Hive的体验&Hive服务端和客户端的使用方法。 一、Hive与hadoop直接的关系 Hive利用HDFS存储数据,利用MapReduce查询数据。 二、Hive与传统数...

em_aaron
昨天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部