专栏首页小浩算法《剑指offer》第12天:旋转数组的最小数字

《剑指offer》第12天:旋转数组的最小数字

旋转数组的最小数字

题目描述

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

**NOTE:**给出的所有元素都大于 0,若数组大小为 0,请返回 0

解法

解法一

直接遍历数组找最小值,时间复杂度 O(n),不推荐。

public class Solution {
    /**
     * 获取旋转数组的最小元素
     * @param array 旋转数组
     * @return 数组中的最小值
     */
    public int minNumberInRotateArray(int[] array) {
        if (array == null || array.length == 0) {
            return 0;
        }

        int n = array.length;
        if (n == 1 || array[0] < array[n - 1]) {
            return array[0];
        }

        int min = array[0];
        for (int i = 1; i < n; ++i) {
            min = array[i] < min ? array[i] : min;
        }

        return min;
    }

}

解法二

利用指针 p,q 指向数组的首尾,如果 array[p] < array[q],说明数组是递增数组,直接返回 array[p]。否则进行如下讨论。

计算中间指针 mid

  • 如果此时 array[p], array[q], array[mid] 两两相等,此时无法采用二分方式,只能通过遍历区间 [p,q] 获取最小值;
  • 如果此时 p,q 相邻,说明此时 q 指向的元素是最小值,返回 array[q]
  • 如果此时 array[mid] >= array[p],说明 mid 位于左边的递增数组中,最小值在右边,因此,把 p 指向 mid,此时保持了 p 指向左边递增子数组;
  • 如果此时 array[mid] <= array[q],说明 mid 位于右边的递增数组中,最小值在左边,因此,把 q 指向 mid,此时保持了 q 指向右边递增子数组。
public class Solution {
    /**
     * 获取旋转数组的最小元素
     * @param array 旋转数组
     * @return 数组中的最小值
     */
    public int minNumberInRotateArray(int[] array) {
        if (array == null || array.length == 0) {
            return 0;
        }

        int p = 0;
        // mid初始为p,为了兼容当数组是递增数组(即不满足 array[p] >= array[q])时,返回 array[p]
        int mid = p;
        int q = array.length - 1;
        while (array[p] >= array[q]) {
            if (q - p == 1) {
                // 当p,q相邻时(距离为1),那么q指向的元素就是最小值
                mid = q;
                break;
            }
            mid = p + ((q - p) >> 1);

            // 当p,q,mid指向的值相等时,此时只能通过遍历查找最小值
            if (array[p] == array[q] && array[mid] == array[p]) {
                mid = getMinIndex(array, p, q);
                break;
            }

            if (array[mid] >= array[p]) {
                p = mid;
            } else if (array[mid] <= array[q]) {
                q = mid;
            }
        }

        return array[mid];


    }

    private int getMinIndex(int[] array, int p, int q) {
        int minIndex = p;
        for (int i = p + 1; i <= q; ++i) {
            minIndex = array[i] < array[minIndex] ? i : minIndex;
        }
        return minIndex;
    }
}

测试用例

  1. 功能测试(输入的数组是升序排序数组的一个旋转,数组中有重复数字或者没有重复数字);
  2. 边界值测试(输入的数组是一个升序排序的数组,只包含一个数字的数组);
  3. 特殊输入测试(输入空指针)。

内容展示:

本文分享自微信公众号 - 小浩算法(xuesuanfa),作者:程序员小浩

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-08-18

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 剑指offer 03:二维数组中的查找

    在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个...

    程序员小浩
  • 漫画:删除链表倒数第N个节点(二次修订版)

    哨兵节点,捞干货,其实就是一个附加在原链表最前面用来简化边界条件的附加节点,它的值域不存储任何东西,只是为了操作方便而引入。

    程序员小浩
  • 《剑指offer》第23天:删除链表倒数第N个节点

    哨兵节点,其实就是一个附加在原链表最前面用来简化边界条件的附加节点,它的值域不存储任何东西,只是为了操作方便而引入。

    程序员小浩
  • Day13 :调整数组顺序使奇数位于偶数前面

    思路一:   根据题意可知,我们不仅要让奇数在偶数的前面,还要考虑奇数和偶数原来的相对位置不变。因此我们首先要寻找第一个奇数,并将其放在0号位置。然后将第一个...

    stefan666
  • python 快排算法

    先说两句题外话,一般意义上的栈有两层含义,一层是后进先出的数据结构栈,一层是指函数的内存栈,归根结底,函数的内存栈的结构就是一个后进先出的栈。汇编代码中,调用一...

    葫芦
  • php去重后重新排键值

    因为我们已经移除了一些元素,因此数组看起来不是正常的序列。比如我们可能会得到:array(0=>’A’,2=>’B’,5=>’C’);。在某些情况下,这不是一个...

    梦_之_旅
  • PHP数组函数

    白胡杨同学
  • 冒泡排序算法(Bubble Sort)

             对比相邻的元素值,如果满足条件就交换元素值,把较小的元素移动到数组的前面,把大的元素移动到

    itlemon
  • PHP | 删除数组中指定索引的元素,并且重排索引

    凌川江雪
  • 快速排序的四种python实现

    快速排序算法,简称快排,是最实用的排序算法,没有之一,各大语言标准库的排序函数也基本都是基于快排实现的。

    py3study

扫码关注云+社区

领取腾讯云代金券