【剑指offer】7.旋转数组的最小数字

W4n9Hu1 发布于2019-08-23 14:48 / 1215人阅读

摘要：题目把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组为的一个旋转，该数组的最小值为。出现这种情况的类似，此时最小数字一定在的右边。

题目

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

基本思路

肯定不能直接遍历，失去了这道题的意义

旋转数组其实是由两个有序数组拼接而成的，因此我们可以使用二分法，只需要找到拼接点即可。

(1)array[mid] > array[high]:

出现这种情况的array类似[3,4,5,6,0,1,2]，此时最小数字一定在mid的右边。
low = mid + 1

(2)array[mid] == array[high]:

出现这种情况的array类似 [1,0,1,1,1] 或者[1,1,1,0,1]，此时最小数字不好判断在mid左边
还是右边,这时只好一个一个试。
high = high - 1

(3)array[mid] < array[high]:

出现这种情况的array类似[2,2,3,4,5,6,6],此时最小数字一定就是array[mid]或者在mid的左
边。因为右边必然都是递增的。
high = mid

代码

function minNumberInRotateArray(arr)
{
    let len = arr.length;
    if(len == 0)  return 0;
    let low = 0, high = len - 1;
    while(low < high) {
        let mid = low + Math.floor((high-low)/2);
        if(arr[mid] > arr[high]) {
            low = mid + 1;
        } else if(arr[mid] == arr[high]) {
            high = high - 1;
        } else {
            high = mid;
        }
    }
 
    return arr[low];
}

扩展

二分查找

        function binarySearch(data, arr, start, end) {
            if (start > end) {
                return -1;
            }
            var mid = Math.floor((end + start) / 2);
            if (data == arr[mid]) {
                return mid;
            } else if (data < arr[mid]) {
                return binarySearch(data, arr, start, mid - 1);
            } else {
                return binarySearch(data, arr, mid + 1, end);
            }
        }

云服务器 GPU云服务器旋转数组数组中未出现的数字二维数组旋转数组最小值

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/101168.html

剑指Offer(Java版) 持续更新中

摘要：面试题从尾到头打印链表输入一个链表，从尾到头打印链表每个节点的值面试题重建二叉树输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。例如输入前序遍历序列和中序遍历序列，则重建二叉树并返回。队列中的元素为类型。其中负数用补码表示。面试题2 单例(之前有整理，略) 面试题3 二维数组中的查找 public boolean find(int target, int [][] arra...

justCoding 2019-08-15 11:04 评论0 收藏0
LeetCode 精选TOP面试题【51 ~ 100】

摘要：有效三角形的个数双指针最暴力的方法应该是三重循环枚举三个数字。总结本题和三数之和很像，都是三个数加和为某一个值。所以我们可以使用归并排序来解决这个问题。注意因为归并排序需要递归，所以空间复杂度为 ...

Clect 2021-11-15 11:38 评论0 收藏0
剑指offer--JavaScript版

摘要：剑指在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。例如输入前序遍历序列和中序遍历序列，则重建二叉树并返回。其中负数用补码表示。本文为8月牛客网《剑指 offer》刷题做得，现整理出来作为参考。虽然是算法题，但本文用 JavaScript 编写，看了《剑指 offer》以后发现很多问题处理的过程并不是最好的，所以本文仅供参考。以前全部代码 A...

MarvinZhang 2019-08-23 11:52 评论0 收藏0
剑指offer(javascript版)

摘要：二维数组中的查找在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。例如输入前序遍历序列和中序遍历序列，则重建二叉树并返回。 1.二维数组中的查找在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数...

imtianx 2019-08-20 15:20 评论0 收藏0
LeetCode 剑指 Offer 轮转数组转旋转字符串

摘要：请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串和数字，该函数将返回左旋转两位得到的结果。目录第一题:左旋转字符串解题思路: 画图解析: 代码实现: 第二题:轮转数组解题思路: 画图解析: 代码实现: 第一题:左旋转字符串 LeetCode 剑指 Offer 58: 描述:...

Brenner 2021-11-24 09:39 评论0 收藏0