寻找旋转排序数组中的最小值

题意

假设一个旋转排序的数组其起始位置是未知的(比如 0 1 2 4 5 6 7 可能变成是 4 5 6 7 0 1 2)。

你需要找到其中最小的元素。

你可以假设数组中不存在重复的元素。

样例

给出 [4,5,6,7,0,1,2] 返回 0

代码实现: 顺序查找

public class Solution {
    /**
     * @param nums: a rotated sorted array
     * @return: the minimum number in the array
     */
    public int findMin(int[] nums) {
        int i = nums[0];
        for(int j = 1; j < nums.length; j++ ) {
            if(nums[j] < i)
                i = nums[j];
        }
        return i;
    }
}

这种方式非常简单,就是依次顺序查找,但是题目推荐的是用二分法进行查找,故下方又用二分法实现了功能。

代码实现: 二分法

public class Solution {
    /**
     * @param nums: a rotated sorted array
     * @return: the minimum number in the array
     */
    public int findMin(int[] nums) {
        int l = 0;
        int r = nums.length-1;
        if (nums[l] < nums[r])  
            return nums[l];
        
        while (l < r) {
            int mid = (l + r) / 2;
            if (nums[mid] > nums[r])
                l = mid + 1;
            else
                r = mid;
        }
        
        return nums[r];
    }
}

该题的主要思路就是 中位数右侧数 的比较。 根据该类型数据的规律可得结论: 中位数 > 右侧数 则说明 最小数 在右侧,反之在左侧。

原题地址

LintCode:寻找旋转排序数组中的最小值

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

HUST 1586 数字排列

1586 - 数字排列 时间限制:1秒 内存限制:128兆 91 次提交 36 次通过 题目描述现有n个k位的数字,你的任务是重新安排数字每一位的位置,使得...

29912
来自专栏开发与安全

从零开始学C++之STL(四):算法简介、7种算法分类

一、算法 算法是以函数模板的形式实现的。常用的算法涉及到比较、交换、查找、搜索、复制、修改、移除、反转、排序、合并等等。 算法并非容器类型的成员函数,而是一...

2040
来自专栏Python小屋

Python内置函数int()高级用法

int()函数常用来把其他类型转换为整数,例如: >>> int(3.2) 3 >>> int(1/3) 0 其实,int是Python内置类型之一,之所以能...

3067
来自专栏mathor

LeetCode325.最大子数组之和为k

 这道题暴力很好做,但是找技巧确实不好想,首先假设这么一个场景,从下标为0到下标为100,和sum = 2000,假设我们要求的目标k=800,那么我们只要...

2843
来自专栏大数据和云计算技术

二分查找

算法是基础,小蓝同学准备些总结一系列算法分享给大家,这是第5篇《二分查找》,非常赞!希望对大家有帮助,大家会喜欢! 前面系列文章: 归并排序 #算法基础#...

36310
来自专栏数据结构与算法

cf314E. Sereja and Squares(dp)

给你一个擦去了部分左括号和全部右括号的括号序列,括号有25种,用除x之外的小写字母a~z表示。求有多少种合法的括号序列。答案对4294967296取模。 合法序...

1557
来自专栏编程之旅

唠唠快速排序算法

每一个从事计算机相关方向工作的同学一定听说过快速排序算法,在面试的准备过程中,快排也一定是一个必须要牢牢掌握的算法。那么今天就来唠唠快速排序算法。

1082
来自专栏互联网大杂烩

快速排序

快速排序是找出一个元素(理论上可以随便找一个)作为基准(pivot),然后对数组进行分区操作,使基准左边元素的值都不大于基准值,基准右边的元素值 都不小于基准值...

732
来自专栏程序员叨叨叨

5.2 数组类型

在着色程序中,数组通常的使用目的是:作为从外部应用程序传入大量参数到 Cg 的顶点程序中的形参接口,例如与皮肤形变相关的矩阵数组,或者光照参数数组等。

621
来自专栏小樱的经验随笔

HDU 1003 Max Sum【动态规划求最大子序列和详解 】

Max Sum Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (J...

3163

扫码关注云+社区

领取腾讯云代金券