剑指Offer-旋转数组的最小数字

package Array;

/**
 * 旋转数组的最小数字
 * 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。
 * 输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。
 * 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。
 * NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。
 */
public class Solution27 {

    public static void main(String[] args) {
        Solution27 solution27 = new Solution27();
        int[] array = {3, 4, 5, 1, 2};
        System.out.println(solution27.minNumberInRotateArray_2(array));

    }

    /**
     * 二分法,但是要考虑完全旋转和无法判断最小值在那个部位的情况
     *
     * @param array
     * @return
     */
    public int minNumberInRotateArray_2(int[] array) {
        if (array.length == 0 || array == null) {
            return 0;
        }
        int left = 0;
        int right = array.length - 1;
        int mid = 0;
        //旋转过
        while (array[left] >= array[right]) {
            //当left和right两个指针相邻时候,就找到了最小值
            if (right - left <= 1) {
                mid = right;
                break;
            }
            mid = (left + right) / 2;
            //无法确定中间元素是属于前面还是后面的子数组
            if (array[left] == array[mid] && array[right] == array[mid]) {
                return minNumber(array, left, right);
            }
            //array[mid]在左边序列
            if (array[mid] >= array[left]) {
                left = mid;
            } else if (array[mid] <= array[right]) {//array[mid]在右边序列
                right = mid;
            }
        }
        return array[mid];
    }

    private int minNumber(int[] array, int left, int right) {
        int result = array[left];
        for (int i = left + 1; i < right; i++) {
            if (result > array[i]) {
                result = array[i];
            }
        }
        return result;
    }


    /**
     * 暴力
     *
     * @param array
     * @return
     */
    public int minNumberInRotateArray(int[] array) {
        if (array.length == 0 || array == null) {
            return 0;
        }
        int result = array[0];
        for (int i = 1; i < array.length; i++) {
            if (result >= array[i]) {
                result = array[i];
            }
        }
        return result;
    }
}

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏ACM算法日常

将树围起来(几何凸包)- HDU 1392

在二维欧几里得空间中,凸包可想象为一条刚好包著所有点的橡皮圈。如下图所示。计算凸包也就是求得外围(蓝线上)的那些点。

10720
来自专栏Python小屋

Python+numpy实现函数向量化

Python本身对向量操作的支持并不是很好,需要借助列表推导式或函数式编程来实现,例如: >>> import random # 生成随机测试数据 >>> x...

90250
来自专栏chenjx85的技术专栏

leetcode-896-单调数列

如果对于所有 i <= j,A[i] <= A[j],那么数组 A 是单调递增的。 如果对于所有 i <= j,A[i]> = A[j],那么数组 A 是单调递...

14330
来自专栏desperate633

LintCode 单词搜索题目分析代码

单词可以由按顺序的相邻单元的字母组成,其中相邻单元指的是水平或者垂直方向相邻。每个单元中的字母最多只能使用一次。

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

10:单词排序

10:单词排序 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 输入一行单词序列,相邻单词之间由1个或多个空格间隔,请按照...

42170
来自专栏向治洪

数据结构之2-3-4树

2-3-4树是一种阶为4的B树。它是一种自平衡的数据结构,可以在O(lgn)的时间内查找、插入和删除,这里的n是树中元素的数目。2-3-4树和红黑树是等价的,也...

19290
来自专栏深度学习计算机视觉

打印字符图形(蓝桥杯基础题 Java版)

问题描述 利用字母可以组成一些美丽的图形,下面给出了一个例子: ABCDEFG BABCDEF CBABCDE DCBABCD EDCBABC 这...

46360
来自专栏AIUAI

Pytorch - Cross Entropy Loss

4.6K60
来自专栏CDA数据分析师

Python之numpy数组学习(二)

前言 前面我们学习了numpy库的简单应用,今天来学习下比较重要的如何处理数组。 处理数组形状 下面可将多维数组转换成一维数组时的情形。 利用以下函数处理数组的...

31980
来自专栏机器学习从入门到成神

稀疏矩阵转置

矩阵是线性代数中的一个知识,刚开始学习的时候可能感觉不到它有什么用处,最初的感觉就是对二维数据的操作。其实现实生活中矩阵的用处太大了,设计领域相当的广泛。在此只...

30410

扫码关注云+社区

领取腾讯云代金券