【九度OJ1386】|【剑指offer8】旋转数组的最小数字
博客专区 > aqia358 的博客 > 博客详情
【九度OJ1386】|【剑指offer8】旋转数组的最小数字
aqia358 发表于4年前
【九度OJ1386】|【剑指offer8】旋转数组的最小数字
  • 发表于 4年前
  • 阅读 30
  • 收藏 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]);
    		}
    	}
    
    }


共有 人打赏支持
粉丝 6
博文 81
码字总数 30297
×
aqia358
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: