JavaScript 算法，大厂前端面试真题

在今天

面对严峻的求职环境，搞定算法是我们提高职场竞争力/迈过面试算法关的必备技能之一，不要因为做前端，就忽略算法的重要性。

数据结构和算法，是大厂前端面试的“拦路虎”，很多同学都望而生畏。其实如果了解常用数据结构，掌握基本的算法思维，就不难应对

大厂为何要考察算法 ？

如何在短时间之内快速判断一个工程师是否优秀 ？考察算法是最合理的方式，这是行业内多年的经验积累。

前端面试考算法真不是因为内卷 ！其实，算法一直在后端面试中都被考察，现在前端也考查，说明前端能做的工作越来越多了，也越来越重要了，这是好事。

接下来我们开始一步步的提升编程内功，补齐面试中的算法短板。

一、手写 flat 方法，实现数组的扁平化

TIP

flat()方法会按照一个可指定的深度递归遍历数组，并将所有元素与遍历到的子数组中的元素合并为一个新数组返回。

flat();
flat(depth);
// 指定要提取嵌套数组的结构深度，depth 默认值为 1。

• 我们首先来看下 JS 中数组的 flat 方法

var arr = [0, 1, 2, [3, [4, 5], 6], 7, 8, 9];
var arr1 = arr.flat(); // 默认将数组展平1层
console.log(arr1); //  [0, 1, 2, 3, [4, 5], 6, 7, 8, 9]

var arr2 = arr.flat(2); // 将数组展平2层
console.log(arr2); // [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

手写 flat 方法源码：

/**
 *  @param arr 需要扁平化的数组
 *  @param n 指定的扁平化的深度
 *  关于n的类型判断：
 *  - 如果 n 没有传(undefined)，默认值是1
 *  - 如果 n 为正的数字类型字符串，转成对应数字
 *  - 如果 n 为负数，则相当于0
 *  - 如果 n 为true，则表示1  其它都为非数字类型都表示0
 */
function flat(arr, n) {
  // 数据类型判断
  if (!arr.isArray) return;
  if (n === undefined) n = 1;
  var n = Number(n) >= 0 ? Number(n) : 0;
  // 结果数组
  var result = [];
  function fn(arr, n) {
    for (var i = 0; i < arr.length; i++) {
      var item = arr[i];
      if (Array.isArray(arr[i])) {
        // 如果小于等于0 ,递归次数用尽，则不递归，直接推入
        // 重点
        if (n <= 0) {
          result.push(item);
        } else {
          n--; // 递归次数用掉一次，减1
          fn(item, n); //递归
          n++; // 保持同一层级深度不被减掉
        }
      } else {
        result.push(item);
      }
    }
  }
  fn(arr, n);
  return result;
}

var arr = [1, [2], 3, [4, [2, [3]]], [6], [[7], [8, [9]]]];
console.log(flat(arr, Infinity));
console.log(arr.flat(Infinity));

二、将一个数组旋转 k 步

TIP

将数组[1, 3, 5, 7, 9, 11, 13]旋转 K 步

1、审题：理解题目的意思

假设 k=4 ，即旋转 4 步

• 第一步，得到数组 [ 13, 1, 3, 5, 7, 9, 11 ]
• 第二步，得到数组 [ 11, 13, 1, 3, 5, 7, 9 ]
• 第三步，得到数组 [ 9 , 11, 13, 1, 3, 5, 7]
• 第四步，得到数组 [ 7, 9, 11, 13，1, 3, 5]

即数组旋转 4 步后，得到数组[ 7, 9, 11, 13，1, 3, 5]

2、解题思路

针对这个题，我们有以下两个思路

• 方法一：把数组尾部的元素用 pop 方法一个一个删除，然后再用 unshift 方法插到数组的前面
• 方法二：把数组拆分，最后用数组的 concat 方法拼接到一起

3、方法一：去尾插头

/**
 * @description 旋转数组 k步 去尾插头
 * @author 清心老师
 * @param k 旋转次数
 * @param arr 旋转数组
 */
function rotateArr(arr, k) {
  // 获取数组的长度
  var length = arr.length;
  // 判断如果数组长度为0，或k不存在，则直接返回原数组
  if (length === 0 || !k) return arr;
  // k有可能是负数，如果是负数就取绝对值 如-3变 3
  // 如果k的长度大于数组长度时， k%lenght
  var step = Math.abs(k % length);
  // for循环，遍历数组中的每一个数
  for (var i = 0; i < step; i++) {
    var value = arr.pop();
    // 这里不用判断value的值，因为不可能出现删除空的情况
    // 如果要判断可以 if(value!=null){ } 过滤undefined，但0也能通过
    arr.unshift(value);
  }
}
var arr = [1, 3, 5, 7, 9, 11, 13];
rotateArr(arr, 4); //  [7, 9, 11, 13, 1, 3, 5]
console.log(arr);
rotateArr(arr, "4"); //
console.log(arr);
// 考虑k的以下情况：
// k是赋值，k是字符串，k不存在，k为0

4、方法、拆分数组，然后拼接

/**
 * @description 旋转数组 k 步   拆分数组再拼接
 * @author 清心老师
 * @param k 旋转次数
 * @param arr 旋转数组
 */
function rotateArr(arr, k) {
  // 获取数组的长度
  var length = arr.length;
  // 判断如果数组长度为0，或k不存在，则直接返回原数组
  if (length === 0 || !k) return arr;
  // k有可能是负数，如果是负数就取绝对值 如-3变 3
  // 如果k的长度大于数组长度时， k%lenght
  var step = Math.abs(k % length);
  // 数组的前半部分
  var arrPart1 = arr.slice(0, length - step);
  // 数组的后半部分 arr.slice(-3);从后往前取3个
  var arrPart2 = arr.slice(-step);
  return arrPart2.concat(arrPart1);
}
var arr = [1, 3, 5, 7, 9, 11, 13];
var arr2 = rotateArr(arr, 3);
console.log(arr2); //  [9, 11, 13, 1, 3, 5, 7]

5、两种方式的复杂度分析

TIP

• 思路 1：时间复杂度是 O(n²) 、空间复杂度 O(1)， 为什么呢？
• 思路 2：时间复杂度是 O(1)、空间复杂度是 O(n)

提示：

我们所前端是重时间，轻空间，思路 1 的时间复杂度 O(n²) ，这个是完全不能接受的。

6、性能测试

// 性能测试
var arr = [];
for (var i = 0; i < 100 * 1000; i++) {
  arr.push(i);
}
console.time("rotate");
rotateArr(arr, 4000);
console.timeEnd("rotate");

对比

• 当旋转次数相同，都是 4000 次时
  • 思路 1 耗时：50.336181640625 ms
  • 思路 2 耗时：0.713134765625 ms
• 当旋转次数为 40000 次时
  • 思路 1 耗时：515.923095703125 ms
  • 思路 2 耗时：1.344970703125 ms
• 随着数据规模量变大和旋转次数的增多，思路 2的耗时变化不大，但思路 1的耗时巨增。

在前端领域是重时间轻空间的，所以我们肯定首先思路 1

三、字符串中括号匹配是否正常

TIP

判断一个字符串中的括号{} [] ()是否匹配正常，这是一个非常经典的面试题。

我们先来审下题，看如何匹配才算是正常匹配的呢？

1、审题：理解题目的意思

TIP

• 字符串 1 :匹配是正常的
• 字符串 2： 匹配失败，如果]在}前，就是正常的

2、解题思路

这个问题本质是在考查什么呢 ？

他是在考你理不理解栈这种数据结构，如果你会，那这个题就很容易做了。

所以我们先来了解下，栈这种数据结构，然后再回过头来看，这道题如何解。

2.1、什么是栈

TIP

• 栈是一种先进后出的数据结构，要弄明白什么是栈，我们先举一个生活中的例子来帮助大家理解
• 假如你现在有一个长长的圆筒，圆筒的一端是封闭的，另一端是开口，现在往圆筒底部放气球，那先放的是不是在圆筒的底部，后放的是不是在靠近圆筒的位置

如下图：

注：

我们现在要从圆筒中取出气球，那我们是不是得先取离圆筒出口最近的一个，即取球时的顺序正好和放的时候的顺序是反的。

我们把圆筒比喻从栈，那放气球的过程叫入栈，拿气球的过程叫出栈；
圆筒的底部称为栈底，圆筒出口的第一个气球位置叫栈顶。

总结：

• 栈是什么：栈是一种先进后出的数据结构（逻辑层面）
• 入栈：进栈时，先进去的在底部，后进去的在栈顶
• 出栈：出栈时，先进去的后出，后进去的先出

2.2、数组演示入栈和出栈

TIP

• 如果我们把数组比像想成一个栈结构，那他的第一个元素位置就是栈底，最后一个元素位置就是栈顶
• 然后从后往前 push 元素时，就相当于入栈，从后 pop 删除数据时，就相当于出栈

// 声明一个空数组，用来当成栈
var arr = [];

// 向数组中添加元素
for (var i = 0; i < 6; i++) {
  arr.push(i); // 入栈
  console.log(arr);
}

// 取出数组中的元素
for (var i = 0; i < 6; i++) {
  arr.pop(); // 出栈
  console.log(arr);
}

2.3、栈和数组的关系

TIP

本质上栈和数组完全不是一个层面上的东西，是不能拿 来做比较的

• 栈：是一种逻辑结构，是一种理论模型，他是抽像出来的一种结构。
• 数组：数组是一种物理结构，是实实在在存在的，可能用来操作的和存储数据的，同时还提供了相关的 API，让我们来操作数组。

我们有很多种方式来实现栈这种结构来存储和取数据等，其中数组就可以实现栈这种结构来存储和操作数据。

3、利用栈结构思想来解题

TIP

• 我们可以用 for 循环来遍历字符串中的每一个字符串
• 遇到左括号 { ( [就压栈
• 遇到右括号] ) } ，就判断栈顶是否与当前括号匹配，匹配就出栈
• 最后判断栈中数据的 length 长度是否为 0，如果不为 0，则不匹配，为 0 就匹配成功

字符串：的整个入栈和出栈过程实现如下

代码实现

// 判断字符串是否括号匹配
function matchBracket(str) {
  // 不管什么类型，进来先转成字符串
  str = str + "";
  // 获取字符串长度
  var len = str.length;
  // 如果长度为0，则直接返回true
  if (len === 0) return true;

  // 定义一个数组，来当栈，左括号入栈
  var stack = [];
  // 定义一个变量用来放左括号的字符串
  var leftSymbols = "{[(";
  // 定义一个变量用来放右括号的字符串
  var rightSymbols = ")]}";

  // for循环遍历每个字符串
  for (var i = 0; i < len; i++) {
    // 取出每一个字符
    var s = str[i];
    if (leftSymbols.includes(s)) {
      // 判断是左括号，就压栈
      stack.push(s);
    } else if (rightSymbols.includes(s)) {
      // 是右括号，取出栈顶的元素
      var stackTop = stack[stack.length - 1];
      // 判断右括号是否与栈顶匹配，匹配就出栈
      if (isMatch(stackTop, s)) {
        stack.pop();
      } else {
        // 如果不匹配，直接返回false，也就意示着整个字符串括号不匹配
        return false;
      }
    }
  }
  // 如果为0，匹配成功，返回true，不匹配就返回false
  return stack.length === 0;
}
// 检测栈顶元素与当前右括号元素是否匹配
function isMatch(left, right) {
  if (left === "{" && right === "}") return true;
  if (left === "[" && right === "]") return true;
  if (left === "(" && right === ")") return true;
  return false;
}

var str = "a{(b{c[1,2,3]})}";
var bool = matchBracket(str);
console.log(bool);

4、算法复杂度分析

TIP

• 时间复杂度 O(n)

整个过程就一次 for 循环，其内部的 includes 判断，其遍历次数不受输入量的影响，一直是 3 次

• 空间复杂度 O(n)

主要是要用一个变量 stack 来存储入栈的数据，其大小不会完全受输入量的影响，但是输入量大，也是有一定影响的，所以定为 O(n)

没有其它方法与此对比，所以性能测试没有对比的可能性。

四、找出一个数组中和为 n 的两个数

TIP

给出一个有序的递增数组，找出数组中和为 n 的两个数的所有情况

1、审题

如：

• 找出数组[1,3,5,7,10,13,15,20,22,25]中和为 20 的两个数的所有情况
• 满足条件的有两组：5 和 15 是一组，7 和 13 是一组

2、解题思路

TIP

• 方法一：嵌套循环，找到一个数，然后和数组中的其它数都加一遍，如果和为 20，则就保存这两个数
• 方法二：利用单层 for 循环+双指针来实现。

3、方法一：两层 for 循环嵌套

TIP

for 循环嵌套查找，也不是说，一定要全部都遍历完，因为是有序的，所有只要找到一组满足要求的元素后，后面的查找范围其实是一直在缩小的。

如下

function findTowNumber(arr, n) {
  var result = []; // 用来存入符合要求的元素
  if (!Array.isArray(arr)) return result;
  if (isNaN(n)) return result;
  var len = arr.length - 1;
  var maxLen = arr.length; // 记录上一次找到的元素的下标，确定下次查找的范围
  for (var i = 0; i < arr.length; i++) {
    for (var j = i + 1; j < maxLen; j++) {
      var sum = arr[i] + arr[j];
      if (sum == 20) {
        var obj = {};
        obj.a = arr[i];
        obj.b = arr[j];
        result.push(obj);
        maxLen = j; // 因为是升序，所以下次查找的范围，肯定要小于第一次找到的元素下标
        break; // 找到就退出
      }
    }
  }
  return result;
}

var arr = [1, 3, 5, 7, 10, 10, 10, 13, 15, 20, 22, 25];

4、方法二：for 循环+双指针

指针：

• 在汉语里，指钟表、仪器上面指示时间和度数的针
• 在程序中，指针就是一个变量，相当于保持了对某一数据的引用

比如，你定义了两个变量，分别保存数组中的两个不同的元素，就相当于定义了两个指针，分别用来指向数组中的不同元素。

双指针解题思路

我们以查找数组 arr = [1,3,5,7,10,13,15,20,22,25]中和为 20 的两个数的所有情况为例来讲解

这是一个递增的数组 arr，我们定义两个变量i=0 ;j=数组长度-1

• 如果arr[i] + arr[j] > 20 则 j--
• 如果arr[i] + arr[j] < 20 则i++
• 如果arr[i] + arr[j] = 20则找到了一组满足要求的数，保存arr[i]和arr[j]，同时i++,j--，继续查找

在这里，你可以把i和j理解为两个指针，因为我们是通过修改i和j的值，来更改arr[i]和arr[j]对数组中数据的引用

注：

当 i = j 时，两者重合，就没有查找的必要，所以当i < j时，一直查找

代码实现

function findTowNumber(arr, n) {
  var result = []; // 用来存入符合要求的元素
  if (!Array.isArray(arr)) return result;
  if (isNaN(n)) return result;
  var len = arr.length - 1;
  var i = 0;
  var j = len - 1;
  while (i < j) {
    var sum = arr[i] + arr[j];
    if (sum > n) {
      j--;
    } else if (sum < n) {
      i++;
    } else {
      // 用对象来保存每次符合要求的一组元素
      var obj = {};
      obj.a = arr[i];
      obj.b = arr[j];
      result.push(obj); // 把符合要求的一组数据push到数组中
      i++;
      j--;
    }
  }
  return result;
}

var arr = [1, 3, 5, 7, 10, 10, 13, 15, 20, 22, 25];
console.log(findTowNumber(arr, 20));

5、算法复杂度分析

TIP

• 第一种方式：时间复杂度介于 O(n) 与 O(n^2) 之间，如果查找的两数之后比较大，则每次要遍历到数且的最后面才能找到对应的数，如果查找的两数之后较小，则时间复杂度就低，因为很快就找到，并且后面的查找范围也会相应索小
• 第二种方式：时间复杂度为 O(n)

两者的空间复杂度都为 O(1) ，其内存占用，并不因为 arr 增大而成倍成大。

6、性能测试

var arr = [1, 3, 5, 7, 10, 10, 10, 13, 15, 20, 22, 25];
console.time("双层for循环");
for (var i = 0; i < 1000 * 100; i++) {
  findTowNumber(arr, 45);
}
console.timeEnd("双层for循环");

五、二分法找查数组的的某个元素

TIP

我们要查找有序数组 [1,3,4,5,7,8,9,12,15,18,30,32,45] 中元素值为 15 的元素的下标。

1、审题：理解题目的意思

TIP

• 比如，要找到数组中元素为 5 的下标，则 5 的下标是 3
• 比如，要找到数组中元素为 9 的下标，则 9 的下标是 6

2、解题思路

思路一：for 循环遍历查找

最简单的方式，就是通过一次 for 循环的遍历，拿当前值与数组中的每个值一个一个做比较，如果全等，则就返回当前数组中元素的下标

思路二：二分查找

每一次都从剩下元素的中间位置开始查找。

3、二分查找过程演示

TIP

如果我们要用二分法来查找到 15 在数组[1,3,4,5,7,8,9,12,15,18,30,32,45]中的下位置。

我们来看下，会始何查找

3.1、第一次查找

TIP

先从数组的最中间元素9开始找，把当前值15与数组中中间元素9比较

• 如果当前值15大于9，则往15的右边查找
• 如果当前值15小于9，则往15的左边查找
• 如果当前值15等于9，则找到该元素，直接返回元素下标

显然 15 大于 9，则下一轮要在 9 的右边查找

这一轮 startIndex=0 endindex=12 midIndex=(0+12)/2=6

3.2、第二次查找

TIP

把当前值15与9右边部分的中间位置元素18比较，即拿15与18比较

• 如果当前值15大于18，则往18的右边查找
• 如果当前值15小于18，则往18的左边查找
• 如果当前值15等于18，则找到该元素，直接返回元素下标

显然 15 小于 18，则下一轮要在 18 的左边查找

这一轮startIndex=6+1=7 endIndex=12 midIndex=Math.floor((7+12)/2)=9

3.3、第三次查找

TIP

把当前值15与18左边部分的中间位置元素 15 比较，即拿15与15比较

• 如果当前值15大于15，则往15的右边查找
• 如果当前值15小于15，则往15的左边查找
• 如果当前值15 等于15，则找到该元素，直接返回元素下标

显然 15 等于 15 找到了，就不查找了

这一轮startIndex=7 endIndex=midIndex-1=8 midIndex=Math.floor((7+8)/2)=7

从上面我们发现

如果当 midIndex === endIndex时，如果还找不到，说明数组中不存在这个元素

3.4、总结二分查找规律

TIP

• 我们每一次都要从中间位置查找，所以我们需要有办法得到中间位置元素
• 我们定义三个变量 startIndex、endIndex、midIndex 分表来记录当前的起始、结束、中间下标
• 刚开始 startIndex 和 endIndex 的值是知道的，startIndex = 0, endIndex = arr.length - 1
• 通过公式 midIndex = Math.floor((starIndex+endIndex/2)) ，得到中间元素下标，获取中间元素

如果，当前值 > 中间值 ，则下一轮在中间值右边部分的中间查找，这时

• startIndex = midIndex + 1;
• endIndex值不变
• midIndex = Math.floor((startIndex+midIndex)/2)

如果，当前值 < 中间 ，则下一轮在中间值的左边部分中间查找，这时

• startIndex 不变
• endIndex = midIndex - 1;
• midIndex = Math.floor((startIndex+midIndex)/2)

如果，当前值 === 中间值 ，则找到，返回midIndex ，即元素下标

如果，一轮找下来 ，当midIndex === endIndex时还找不到元素，则说明当前值不在数组中。

上面要重复循环做相同的事，但是我们并不能确定具体的循环次数，所以这里我们不用 for 循环，选用 while 循环，因为我们只要知道什么时结束，就可以一直循环下startIndex <= endIndex

4、二分法 + while 循环代码实现

// 二分查找，查找number在数组arr中的下标,找不到返回-1
function binarySearch(arr, number) {
  // 不是数组，直接返回
  if (!Array.isArray(arr)) return -1;
  var length = arr.length;
  // 数组为空，直接返回
  if (length === 0) return -1;

  var startIndex = 0; // 起始下标
  var endIndex = length - 1; // 结束下标

  while (startIndex <= endIndex) {
    // 中间下标
    var midIndex = Math.floor((startIndex + endIndex) / 2);
    // 中间值
    var midValue = arr[midIndex];

    if (number < midValue) {
      endIndex = midIndex - 1; // 当前值小于中间值，左边找
    } else if (number > midValue) {
      startIndex = midIndex + 1; // 当前值大于中间值，右边找
    } else {
      return midIndex; // 当前值等于中间值，找到，返回下标
    }
  }
  return -1; // while中找不到时，才会执行这一句，即找不到元素
}

var arr = [1, 3, 4, 5, 7, 8, 9, 12, 15, 18, 30, 32, 45];
var i = binarySearch(arr, 15);
console.log(i);

5、二分 + 递归实现

/**
 * binarySearch 二分查找
 * @param arr 要查找的数组
 * @param number 要查找的数
 * @param startIndex 数组查找的开始位置，如果不传默认为0
 * @param endIndex 数组查找的结束位置，如果不传默认为数组长度-1
 */
function binarySearch(arr, number, startIndex, endIndex) {
  // 判断 arr是不是数组  同时长度如果为0
  if (!Array.isArray(arr) || arr.length == 0) return -1;
  // undefined==null是true
  if (endIndex == null) endIndex = arr.length - 1;
  // 这里还要考虑传过来的参数 startIndex和endIndex的类型处理
  // 大家参考手写的slice方法来处理，(在面向对象原型和原型链那里），两者代码实现上一模一样

  // 递归的结束条件,当startIndex大于endIndex时，还没有找到，则返回-1
  if (startIndex > endIndex) return -1;
  var midIndex = ((startIndex + endIndex) / 2) >> 0; //向下取整
  // 用当前值与中间值来做比较
  if (number > arr[midIndex]) {
    return binarySearch(arr, number, midIndex + 1, endIndex);
  } else if (number < arr[midIndex]) {
    return binarySearch(arr, number, startIndex, midIndex - 1);
  } else {
    // 相等，就找到，返回当前下标
    return midIndex;
  }
}
var arr = [1, 3, 4, 5, 7, 8, 9, 12, 15, 18, 30, 32, 45];
console.log(binarySearch(arr, 15));

6、算法复杂度分析

TIP

• 二分法+while 和 二分+递归 的时间复杂度是O(logn)空间复杂度都是O(1)级别
• 但循环要比递归在性能上更好，因为递归在内部会一直调用函数，所以会更消耗性能。
• 递归代码逻辑更清晰

7、性能测试

// 执行1000 *1000次 查看两则的执行效率
console.time("递归");
for (var i = 0; i < 1000 * 100; i++) {
  binarySearch(arr, 15);
}
console.timeEnd("递归");

console.time("while");
for (var i = 0; i < 1000 * 100; i++) {
  binarySearch(arr, 15);
}
console.timeEnd("while");

总结:

• 只要是有序查找，则必定考虑必二分 ！
• 只要是二分查找，时间复杂度必包含 O(logn)

六、求字符串中连续最多的字符，以及次数

TIP

求以字符串aaabbccddaaaaaffffdddd中，连续出现最多的字符及字数 （以最先出现的为主）

1、审题

TIP

以下字符串中连续出现最多的字符是a ，及次数是5

2、解题思路

TIP

• 方法一：for 循环嵌套 + 跳步思想来解决
• 方法二：for 循环 + 双指针

3、方法一： for 循环嵌套+跳步

TIP

我们以下面这个字符串的查找为例，来讲下解 for 循环嵌套+跳步的方式是如何实现的

• 用两层 for 循环来遍历元素，取出每一个元素，与原字符串做比较，如下图
• count 用来临时存储连续相同字符出现的次数
• 定义变量 var obj = {char:'',len=0} 用来保存连续出现最多的字符及次数

3.1、第一次循环比较

解析：

• 当str[i]===str[j]时，count++;
• 当str[i]!==str[j]时 ， 比较obj.len与count的值

如果 obj.len < count ，更新 obj.len = count = 3 ， obj.char = str[i] = 'a' ，同时 i = j - 1 ，然后退出 for 循环

3.2、第二次循环比较

解析：

首先要重置 count=0;

• 当str[i] === str[j]时 ，count++;
• 当str[i] !== str[j]时 ， 比较obj.len与count的值，如果obj.len > count ，不做任何更新 ，退出当前 for 循环

......中间省略很多步，比较方法和前两步一样

3.3、最后一次循环比较

注意：

最后一次比较，如果最后的字符是多个连续字符，那比较结果相等时，也是要更新数据的

if (str[j] == str.length - 1) {
  // 也需要比较判断字符出现的次数与最大字符出现的次数
}

3.4、代码实现思路

TIP

• 我们这里要存两个值，一个是出现字符，一个是字符的次数，所以我们可以用一个对象来存。

// 变量obj，用来保存出现次数最多的字符及次数
var obj = {char:'',len=0}

• 我们要统计每一次查找的元素临时出现的重复次数，则需要定义一个变量来存储

var count = 0; // count用来临时存储每一次查找的元素出现的次数

然后利用 for 循环，遍历出每个字符，然后把每个字符与原字符串作比较

• 如果相等，则统计次数加 1，即 count++
  
• 如果不相等，则把当前统计的次数与obj.len作比较
  
• 如果obj.len > count ，则更新 count 的值，同时更新 i 和 j 的值，开始下一个字符的比较

具体代码实现如下：

for (var i = 0; i < str.length; i++) {
  for (var j = i; j < str.length; j++) {
    // 判断两者是否相等
    if (str[i] === str[j]) {
      count++;
    }
    if (str[i] !== str[j]) {
      // 比较两者大小，决定是否更新值
      if (obj.len < count) {
        obj.len = count;
        obj.char = str[i];
        i = j - 1;
      }
      break;
    }
  }
}

要特别注意

• 最后一次比较，如果最后的字符是多个连续相同字符，那比较结果相等时，也是要更新数据的
• 如果字符串中只有一个字符时，其第一次比较也就是最后一次比较，两都也是相等，也要更新数据

完整代码实现

/**
 * 统计连续出现重复字符次数最多的字符和次数，利for循环 +跳步方式实现
 * @param str 传入字符
 */
function findContinuousChar(str) {
  // 不管传入的是啥，统一转成字符串
  str = str + "";
  // obj用来存储连续出现字符最多的字符和次数
  var obj = {
    char: "",
    len: 0,
  };
  // 如果字符串长度为0
  if (str.length === 0) return obj;
  // 临时记录当前连续字符的长度,最少出现1次
  var count = 0;
  for (var i = 0; i < str.length; i++) {
    // 每一次循环，重置count的值为0
    count = 0;
    for (var j = i; j < str.length; j++) {
      if (str[i] === str[j]) {
        count++;
      }
      // 如果比较到数组的最后一个元素是相等的，也要更新数据
      if (str[i] !== str[j] || j === str.length - 1) {
        if (obj.len < count) {
          obj.char = str[i];
          obj.len = count;
        }
        // 写在外面，否则会进入死循环
        if (j < str.length - 1) {
          i = j - 1;
        }
        break; // 不相等或最后一个元素，退出for循环
      }
    }
  }
  return obj;
}

var str = "aaabbccddaaaaaffffdddd";
var obj = findContinuousChar(str);
console.log(obj);

4、方法二：for 循环 + 双指针

TIP

• 我们可以利用 for 循环来遍历字符串，把每个字符串取出来
• 定义变量 count 统计临时出现的次数
• 定义变量 obj = {char:'',len=0} 来记录连续出现次数最多的字符及次数
• 我们定义两个变量，i 和 j，相当两个指针，最开始两个字符串指向同一个元素

4.1、第一轮比较

拿 i 对应的元素 与 j 对应的元素作比较

• 如果相等，则累加 i 中元素出现次数，同时 i 向右移动
• 如果不相等，或最后一个元素，则要判断 obj.len 与 count 的大小

  如果obj.len < count，则更新 obj 的值
  同时移动指针 j ，使 j = i; i--;

这一轮得到obj = {char='a',len=3} j=3 , i=2

4.2、第二轮比较

与第一轮一样

拿i对应的元素与j对应的元素作比较

• 如果相等，则累加i中元素出现次数，同时i向右移动
• 如果不相等，或最后一个元素，则要判断 obj.len与count的大小

  如果obj.len < count，则更新 obj 的值
  同时移动指针 j ，使 j=i;

这一轮得到 obj = {char='a',len=3} j=5 , i=4

..... 重复以上步骤来比较

4.3、最后一轮比较

要特别注意

最后一次比较，如果最后的字符是多个连续相同字符，那比较结果相等时，也是要更新数据的

4.4、代码实现

function findContinuousChar(str) {
  // 用来存储出现连续次数最多的字符及次数
  var obj = {
    char: "",
    len: 0,
  };
  str = str + ""; // 不管输入的是否是字符串，统一转成字符串
  var len = str.length; // 字符串长度
  if (len === 0) return obj;

  // 定义两个变量，用来做为两个指针，指定元素

  var i = 0;
  var j = 0;
  var count = 0; // 临时记录当前连续字符出现的次数
  for (; i < len; i++) {
    if (str[i] === str[j]) {
      count++;
    }
    // 这里移动的是i，所以要拿i来做判断
    if (str[i] !== str[j] || i === len - 1) {
      // 等于的情况没有处理，则不会进到这里面来
      if (obj.len < count) {
        obj.len = count;
        obj.char = str[j]; // 这里是str[j],不要写成str[i]了
      }
      count = 0; // 重置count的值
      j = i; // 更新j的值，开始下一个字符统计

      if (i < len - 1) {
        i--; // 这里的i--不能放在上面的if中，否则某种情况下会死循环
      }
    }
  }
  return obj;
}
var str = "12345566";
var obj = findContinuousChar(str);
console.log(obj);

总结：

双指针常用于解决嵌套循环

5、算法复杂度分析

TIP

方法一 和 方法二的时间复杂度都为 O(n)，空间复杂度也是 O(1)

6、性能测试

var str = "abcdeffaaabbeeccseesseffff";
console.time("性能测试");
for (var i = 0; i < 1000 * 100; i++) {
  findContinuousChar(str);
}
console.timeEnd("性能测试");

七、快速排序

TIP

采用快速排序的算法，将以下数组[1,33,43,5,76,8,9,12,15,18,30,32,45]按升序来进行排序

1、什么是快速排序？

TIP

• 快速排序是在每一轮排序时，会将数组的中间元素作为基准元素
• 并让其他比基准元素大的元素移到基准元素的一边
• 比基准元素小的元素移到基准元素的另一边

2、快速排序过程演示

TIP

快速排序主要采用二分的思想来实现，我们以下面这个数组为例，来分析速排序的整个的过程

2.1、第一次查找

TIP

• 先从找到数组中的中间元素 9，这个元素就是我们说的基准元素
• 然后遍历数组中的每个元素，每个元素都与9作比较

  所有小于9的元素，放在一个数组 leftArr
  所有大于9的元素，放在另一个数组 rightArr

• 然后将 从左到右，将 leftArr、[9]、rightArr 拼接到一起

2.2、第二次查找

TIP

• 找到 leftArr 数组中的中间元素 5，然后遍历 leftArr 中每个元素与5比较
  • 所有小于5的元素，放在新的数组 leftArr 中
  • 所有大于5的元素，放在新的数组 rightArr 中
• 找到 rightArr 数组的中间元素 15，然后遍历 rightArr 中每个元素与 15 比较
  • 所有小于15的元素，放在新的数组 leftArr 中
  • 所有大于15的元素，放在新的数组 rightArr 中
• 最后然后将 从左到右，将 leftArr、[5]、rightArr [9]、 leftArr 、rightArr 拼接到一起

2.3、第三次查找

TIP

重复前面的找查找过程，第三步查找的结果如下

总结：

• 当 leftArr 和 rightArrr 长度为 1 时，不用再查找和判了
• 如果每找到midValue值为当前数组中的最大值或最小值时，本次排序相当于只排了一个元素，效率也是会很低。

以上图解中，还有一种情况没有考虑到，那就是如果 数组中出现重复的项时，则还需要加一个 midArr 来保存相等的值，以下代码是实现了。

3、解题思路

我们有两种方式来实现

• 方法一：利用递归 + splice() 方法，这种情况会动原数组，返回的是一个新数组
• 方法二：利用递归 + slice()方法，这种情况不会动原数组，返回的是一个新数组
• 方法三：利用递归 + 双指针，这种情况不会动原数组，返回的也是原数组

4、方法一：二分+递归+splice()

function quickSort(arr) {
  if (!Array.isArray(arr)) return;
  // 如果长度为0或1，则不用排序
  if (arr.length === 0 || arr.length === 1) return arr;
  var len = arr.length;
  // 找到中间元素
  var midIndex = Math.floor(len / 2); // 中间元素下标
  var midValue = arr.splice(midIndex, 1)[0]; // 中间元素值

  var leftArr = []; // 放小于中间数的元素
  var rightArr = []; // 大于中间数的元素
  var midArr = []; // 与中间项相等

  // splice方法会删除原数组中元素，所以arr.length长度会时时更新
  for (let i = 0; i < arr.length; i++) {
    var item = arr[i]; // 数组中的每一项
    if (item < midValue) {
      leftArr.push(item); // 小于midValue放leftArr
    } else if (item > midValue) {
      rightArr.push(item);
    } else {
      midArr.push(item);
    }
    // item == midValue 不需要处理
  }
  // 遍历，筛选完后，要开始重组
  return quickSort(leftArr).concat([midValue], midArr, quickSort(rightArr));
}

var arr = [1, 33, 5, 43, 5, 76, 76, 8, 9, 12, 15, 18, 30, 32, 45];
var arr = [1, 5, 33, 8, 9, 99];
var arr1 = quickSort(arr);
console.log(arr1);

5、方法二：快速排序 - 二分+递归+slice()

function quickSort(arr) {
  if (!Array.isArray(arr)) return;
  // 如果长度为0或1，则不用排序
  if (arr.length === 0 || arr.length === 1) return arr;
  var len = arr.length;
  // 找到中间元素
  var midIndex = Math.floor(len / 2); // 中间元素下标
  var midValue = arr.slice(midIndex, midIndex + 1)[0]; // 中间元素值

  var leftArr = []; // 放小于中间数的元素
  var rightArr = []; // 大于中间数的元素
  var midArr = []; // 与中间项相等

  // splice方法会删除原数组中元素，所以arr.length长度会时时更新
  for (let i = 0; i < len; i++) {
    if (i == midIndex) continue; // 如果当前下标和中间下标一样，不操作
    var item = arr[i]; // 数组中的每一项
    if (item < midValue) {
      leftArr.push(item); // 小于midValue放leftArr
    } else if (item > midValue) {
      rightArr.push(item);
    } else {
      midArr.push(item);
    }
    // item==midValue 不需要处理
  }
  // 遍历，筛选完后，要开始重组
  return quickSort(leftArr).concat([midValue], midArr, quickSort(rightArr));
}

var arr = [1, 33, 5, 43, 5, 76, 76, 8, 9, 12, 15, 18, 30, 32, 45];
var arr = [1, 5, 33, 8, 9, 99];
var arr1 = quickSort(arr);
console.log(arr1);

6、方法三：利用递归+双指针

TIP

• 选定当前组组中的第一个元素作为基准元素（pivot）
• 定义两个变量 left 和 right，分别指向数组的第一个元素和最后一个元素
• 接下来进行第一次循环
  • right 指针开始，让指针所指向的元素与基准元素比较。如果大于或等于 pivot，则指针向左移动;如果小于 pivot，则 right 指针停止移动，切换到 left 指针
  • left 指针开始，让指针所指向的元素与基准元素做比较，如果小于等于 pivot，则指针向右移动;如果大于 pivot，则 left 指针停止移动。
  • 当 left 与 right 指针都停止后，让 left 指针和 right 指针所指向的元素进行交换。

循环条件：left !== right 时才循环，即 left >= right，则停止循环

• 接下来重第一次循环的动作，开始第二次循环。
• 一直到 left 与 right 指针重合时（相等时），则让 left 指针指向的元素与 pivot 中元素交换。
• 接下来 left 左边的元素按上面方式来排序，left 右边元素按上面方式来排序

我们以数组[10,9,43,33,8,12,76] 来演示整个循环过程

代码解读

if(left !== right){ 才排序，相等就交换 pivot 基准元素与 left 中的元素 }

下一次左边的元素排序

left = stratIndex right = left-1

下一次右边的元素排序

left = left+1 right = endIndex

function quickSort(arr, startIndex, endIndex) {
  if (startIndex >= endIndex) {
    return;
  }

  // 第一轮排序，得到基准元素
  var pivotIndex = partition(arr, startIndex, endIndex);
  // 根据基准元素，排序左边
  quickSort(arr, startIndex, pivotIndex - 1);
  // 根据基准元素，排序右边
  quickSort(arr, pivotIndex + 1, endIndex);
}

function partition(arr, startIndex, endIndex) {
  // 获取基准元素
  var pivot = arr[startIndex];
  var left = startIndex;
  var right = endIndex;

  // 不相等时
  while (left != right) {
    // 右指针向左移动
    while (left < right && arr[right] > pivot) {
      right--;
    }

    // 左指针向右移
    while (left < right && arr[left] <= pivot) {
      left++;
    }

    // 交换两者的位置
    if (left < right) {
      var temp = arr[left];
      arr[left] = arr[right];
      arr[right] = temp;
    }
  }

  // 相等时
  arr[startIndex] = arr[left];
  arr[left] = pivot;

  return left;
}

var arr = [10, 33, 43, 5, 76, 8, 9, 12, 15, 18, 30, 32, 45];
quickSort(arr, 0, 12);

7、算法复杂度分析

TIP

• 方法一和方法二的时间复杂度是 O(nlogn) ，外层 for 循环是 O(n) ，for 循环里面是二分 O(logn)
• 方法一和方法二的空间复杂度是 O(n)

在这里 splice 和 slice 区分不大

• 第一：算法本身的复杂度 O(n\*logn) 已经很高，所以 splice 和 slice 对于他们来说虽然会增加复杂度，但相对而言影响就不算大
• 第二：splice 和 slice 两者都是二分之后，再执行，二分会快速消减数量级