文档章节

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

aqia358
 aqia358
发布于 2013/10/17 21:31
字数 377
阅读 33
收藏 0
点赞 0
评论 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
博文 81
码字总数 30297
作品 0
海淀
程序员
剑指Offer学习总结-旋转数组的最小数字

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

wwlcsdn000 ⋅ 01/16 ⋅ 0

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

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

qq_28869927 ⋅ 2017/03/29 ⋅ 0

算法知识梳理(4) - 数组第一部分

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

泽毛 ⋅ 2017/11/10 ⋅ 0

算法之路

最近在GitHub上看到的某位学友的算法学习规划,贴过来与各位共勉。有新的内容可以文末留言补充。 学习方法 把所有经典算法写一遍 看算法有关源码 加入算法学习社区,相互鼓励学习 看经典书籍...

李序锴 ⋅ 2017/11/08 ⋅ 0

《剑指offer》面试题04:二维数组中的查找

更多剑指offer面试习题请点击: 《剑指offer》(第二版)题集目录索引 题目:在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,...

tianzez ⋅ 2017/10/19 ⋅ 0

python剑指offer66题

二维数组的查找 替换空格 从头到尾打印链表 重建二叉树 用两个栈实现队列 选择数组中的最小数字 斐波那契数列 跳台阶 变态跳台阶 矩形覆盖 二进制中1的个数 数值的整数次方 调整数组顺序使奇...

lyy0905 ⋅ 06/03 ⋅ 0

《程序员代码面试指南》Python实现(个人读书笔记)

说明   最近一直在读左神的书——《程序员代码面试指南—IT名企算法与数据结构题目最优解》,为了记录自己的学习成果,并且方便以后查看,将自己读书时的想法与使用python实现的代码记录在...

qq_34342154 ⋅ 2017/09/09 ⋅ 0

编程题——1~10

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

thanatos_y ⋅ 2016/07/19 ⋅ 0

剑指Offer学习总结-二维数组寻找数字

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

wwlcsdn000 ⋅ 01/15 ⋅ 0

搜索旋转的排序数组

原题   Follow up for “Search in Rotated Sorted Array”:   What if duplicates are allowed?   Would this affect the run-time complexity? How and why?   Write a function ......

一贱书生 ⋅ 2016/12/19 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

从 Confluence 5.3 及其早期版本中恢复空间

如果你需要从 Confluence 5.3 及其早期版本中的导出文件恢复到晚于 Confluence 5.3 的 Confluence 中的话。你可以使用临时的 Confluence 空间安装,然后将这个 Confluence 安装实例升级到你现...

honeymose ⋅ 16分钟前 ⋅ 0

用ZBLOG2.3博客写读书笔记网站能创造今日头条的辉煌吗?

最近两年,著名的自媒体网站今日头条可以说是火得一塌糊涂,虽然从目前来看也遇到了一点瓶颈,毕竟发展到了一定的规模,继续增长就更加难了,但如今的今日头条规模和流量已经非常大了。 我们...

原创小博客 ⋅ 今天 ⋅ 0

MyBatis四大核心概念

本文讲解 MyBatis 四大核心概念(SqlSessionFactoryBuilder、SqlSessionFactory、SqlSession、Mapper)。 MyBatis 作为互联网数据库映射工具界的“上古神器”,训有四大“神兽”,谓之:Sql...

waylau ⋅ 今天 ⋅ 0

以太坊java开发包web3j简介

web3j(org.web3j)是Java版本的以太坊JSON RPC接口协议封装实现,如果需要将你的Java应用或安卓应用接入以太坊,或者希望用java开发一个钱包应用,那么用web3j就对了。 web3j的功能相当完整...

汇智网教程 ⋅ 今天 ⋅ 0

2个线程交替打印100以内的数字

重点提示: 线程的本质上只是一个壳子,真正的逻辑其实在“竞态条件”中。 举个例子,比如本题中的打印,那么在竞态条件中,我只需要一个方法即可; 假如我的需求是2个线程,一个+1,一个-1,...

Germmy ⋅ 今天 ⋅ 0

Springboot2 之 Spring Data Redis 实现消息队列——发布/订阅模式

一般来说,消息队列有两种场景,一种是发布者订阅者模式,一种是生产者消费者模式,这里利用redis消息“发布/订阅”来简单实现订阅者模式。 实现之前先过过 redis 发布订阅的一些基础概念和操...

Simonton ⋅ 今天 ⋅ 0

error:Could not find gradle

一.更新Android Studio后打开Project,报如下错误: Error: Could not find com.android.tools.build:gradle:2.2.1. Searched in the following locations: file:/D:/software/android/andro......

Yao--靠自己 ⋅ 昨天 ⋅ 0

Spring boot 项目打包及引入本地jar包

Spring Boot 项目打包以及引入本地Jar包 [TOC] 上篇文章提到 Maven 项目添加本地jar包的三种方式 ,本篇文章记录下在实际项目中的应用。 spring boot 打包方式 我们知道,传统应用可以将程序...

Os_yxguang ⋅ 昨天 ⋅ 0

常见数据结构(二)-树(二叉树,红黑树,B树)

本文介绍数据结构中几种常见的树:二分查找树,2-3树,红黑树,B树 写在前面 本文所有图片均截图自coursera上普林斯顿的课程《Algorithms, Part I》中的Slides 相关命题的证明可参考《算法(第...

浮躁的码农 ⋅ 昨天 ⋅ 0

android -------- 混淆打包报错 (warning - InnerClass ...)

最近做Android混淆打包遇到一些问题,Android Sdutio 3.1 版本打包的 错误如下: Android studio warning - InnerClass annotations are missing corresponding EnclosingMember annotation......

切切歆语 ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部