点击蓝色“五分钟学算法”关注我哟

加个“星标”,天天中午 12:15,一起学算法

图解「剑指Offer」之旋转数组的最小数字

作者 | 程序员小吴

来源 | 五分钟学算法

题目描述

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如,数组  [0,1,2,4,5,6,7]  可能变为 [4,5,6,7,0,1,2] )。

请找出其中最小的元素。

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

示例 1:

输入: [3,4,5,1,2]
输出: 1

示例 2:

输入: [4,5,6,7,0,1,2]
输出: 0

题目解析

最直接的方法是使用 暴力法:搜索整个数组,找到其中的最小元素,这样的时间复杂度是 O(N),其中 N 是给定数组的大小。

这道题目可以使用 二分搜索 的思想进行解决。

  • 找到数组的中间元素 mid。

  • 如果中间元素 > 数组第 low 个元素,则在 mid 右边搜索变化点。

  • 如果中间元素 < 数组第 high 个元素,则在 mid 左边搜索变化点。

动画描述

代码实现

//author:程序员小吴
class Solution {
    public int findMin(int[] nums) {
        int low = 0, high = nums.length - 1;
        while (low < high) {
            if (nums[low] < nums[high]) return nums[low];
            int mid = low + (high - low) / 2;
            if (nums[mid] > nums[high]){
               low = mid + 1; 
            } else{
               high = mid;
            } 
          }
        return nums[low];
    }
}

复杂度分析

  • 时间复杂度:O(logN) 。
  • 空间复杂度:O(1)。

知识点

数组、二分法、排序



图解「剑指Offer」之旋转数组的最小数字

● 用好这 42 款 Chrome 插件,每年轻松省出一个年假

● 【算法之美】改变世界的十位算法大师

● 把 14 亿中国人都拉到一个微信群在技术上能实现吗?

● 全球最厉害的 14 位程序员!

—  —

图解「剑指Offer」之旋转数组的最小数字