LeetCode - 面试题11 - 旋转数组的最小数字

86 阅读 0 评论 57 点赞

我是靠谱客的博主秀丽钢笔，最近开发中收集的这篇文章主要介绍LeetCode - 面试题11 - 旋转数组的最小数字，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

一目录

不折腾的前端，和咸鱼有什么区别

目录
一目录
二题目
三解题思路
四统计分析
五解题套路

二题目

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

示例 1：

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

示例 2：

输入：[2,2,2,0,1]
输出：0

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

/**
 * @param {number[]} numbers
 * @return {number}
 */
var minArray = function(numbers) {

};

根据上面的已知函数，小伙伴们可以先尝试破解本题，确定了自己的答案后再看下面代码。

三解题思路

解题 5 分钟，题目很简单。

简单来说，数组中找最小：

已知数组 [1, 2, 3, 4, 5]
那么它旋转会出现：[2, 3, 4, 5, 1]、[4, 5, 1, 2, 3] 等
怎么快速找到最小呢？

且看 jsliang 代码：

const minArray = (numbers) => {
  let min = numbers[0];
  for (let i = 0; i < numbers.length; i++) {
    if (numbers[i + 1] < numbers[0]) {
      return numbers[i + 1];
    }
  }
  return min;
};

假设最小代码为当前数组第一个数字。
顺序遍历数组，找到比第一个数字小的数字之后，那么它就是最小的数字。（关键字：递增有序数组）
如果遍历完毕都没找到，那么就是第一个数字了。

解读完毕。

当然，我们还可以进一步优化：

优化 1（节省空间）

我们为什么需要 min，完全可以不需要啊！

const minArray = (numbers) => {
  for (let i = 0; i < numbers.length; i++) {
    if (numbers[i + 1] < numbers[i]) {
      return numbers[i + 1];
    }
  }
  return numbers[0];
};

优化 2（超级优化）

class Solution {
  public int minArray(int[] numbers) {
    int i = 0, j = numbers.length - 1;
    while (i < j) {
      int m = (i + j) / 2;
      if (numbers[m] > numbers[j]) i = m + 1;
      else if (numbers[m] < numbers[j]) j = m;
      else j--;
    }
    return numbers[i];
  }
}

// 作者：jyd
// 链接：https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/solution/mian-shi-ti-11-xuan-zhuan-shu-zu-de-zui-xiao-shu-3/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

// 优化后 JavaScript
const minArray = (numbers) => {
  let i = 0; j = numbers.length - 1;
  while (i < j) {
    const m = Math.floor((i + j) / 2);
    if (numbers[m] > numbers[j]) {
      i = m + 1;
    } else if (numbers[m] < numbers[j]) {
      j = m;
    } else {
      j--;
    }
  }
  return numbers[i];
};

这位老哥的思路是非常不错的，利用了二分去解题，时间变成 O(log 2N)，极致情况下才是 O(N)。

看来后面得把这些套路都列举出来，要不然脑袋宕机不够用~

四统计分析

本题不做任何分析对比。

五套路分析

本题暂未发现任何套路，如果有但是 jsliang 后面发现了的话，会在 GitHub 进行补充。

如果小伙伴有更好的思路想法，或者没看懂其中某种解法，欢迎评论留言或者私聊 jsliang~

不折腾的前端，和咸鱼有什么区别！

jsliang 会每天更新一道 LeetCode 题解，从而帮助小伙伴们夯实原生 JS 基础，了解与学习算法与数据结构。

浪子神剑 会每天更新面试题，以面试题为驱动来带动大家学习，坚持每天学习与思考，每天进步一点！

扫描上方二维码，关注 jsliang 的公众号（左）和 浪子神剑 的公众号（右），让我们一起折腾！

jsliang 的文档库由梁峻荣采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
基于https://github.com/LiangJunrong/document-library上的作品创作。
本许可协议授权之外的使用权限可以从 https://creativecommons.org/licenses/by-nc-sa/2.5/cn/ 处获得。