专栏首页武培轩的专栏剑指Offer-旋转数组的最小数字

剑指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 条评论
登录 后参与评论

相关文章

  • 排序算法-冒泡排序

    算法简介 冒泡排序(Bubble Sort)是一种典型的交换排序算法,持续比较相邻元素,大的挪到后面,因此大的会逐步往后挪,故称之为冒泡。 算法描述 比较相邻的...

    武培轩
  • 剑指Offer-调整数组顺序使奇数位于偶数前面

    题目描述 输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于位于数组的后半部分,并保证奇数和奇数,偶数和偶...

    武培轩
  • 剑指Offer-二维数组中的查找

    package Array; /** * 二维数组中的查找 * 在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。...

    武培轩
  • Golang 中"泛型"的支持

    Golang不支持一般的类似java中的标记式泛型。很多人因此而十分不满,认为没有泛型增加了很多工作量。而目前由于泛型支持的复杂性,Golang的设计和实现者并...

    李海彬
  • python list定义并初始化长度

    使用Python的人都知道range()函数很方便,今天再用到它的时候发现了很多以前看到过但是忘记的细节。这里记录一下range(),复习下list的slid...

    py3study
  • 常见排序算法-Python实现

    常见排序算法-Python实现 python 排序 算法 1.二分法 python    32行 #coding=utf-8 def binary_s...

    marsggbo
  • jQuery ajax+PHP实现的级联下拉列表框功能示例

    本文实例讲述了jQuery ajax+PHP实现的级联下拉列表框功能。分享给大家供大家参考,具体如下:

    砸漏
  • 浅谈PHP array_search 和 in_array 函数效率问题

    在一个接口中,发现非常耗时,排查原因发现 array_search 查找数组中的元素的 key 时,效率随着数组变大,耗时增加。特别是大数组时,非常耗时。在函数...

    砸漏
  • PHP实现二维数组(或多维数组)转换成一维数组的常见方法总结

    本文实例总结了PHP实现二维数组(或多维数组)转换成一维数组的常见方法。分享给大家供大家参考,具体如下:

    砸漏
  • python--几种快速排序的实现以及运行时间比较

    快速排序的基本思想:首先选定一个数组中的一个初始值,将数组中比该值小的放在左边,比该值大的放在右边,然后分别对左边的数组进行如上的操作,对右边的数组进行如上的操...

    绝命生

扫码关注云+社区

领取腾讯云代金券