2021-前端算法

朴灿烈づ我的快乐病毒、 2022-12-25 08:58 123阅读 0赞

# 前端面试·算法 #

前端面试遇到的一些基本算法问题~总面经可查看：[前端小白的面试问题集][Link 1] ![b7b3da634a6db864e5067222d9123fc7.png][]

# 1 全排列 #

# 2 二分法 #

function BinarySearch (arr, target) {
        let from = 0
        let to = arr.length - 1
        let mid = Math.floor((from + to)/2)
        while (from <= to) {
            mid = Math.floor((from + to)/2)
            if (arr[mid] > target) {
                to = mid - 1
            } else if (arr[mid] < target) {
                from = mid + 1
            } else {
                return mid
            }
        }
    
        return -1
    }

# 3 大整数加法 #

function sumStrings(a,b){
        var res='', c=0;
        a = a.split('');
        b = b.split('');
        while (a.length || b.length || c){
            c += ~~a.pop() + ~~b.pop();
            res = c % 10 + res;
            c = c>9;//c大于9返回1，小于等于为0
        }
        return res.replace(/^0+/,'');
    }

# 4 排序 #

## 4.1 冒泡排序 ##

冒泡排序的基本思想是，对相邻的元素进行两两比较，顺序相反则进行交换，这样，每一趟会将最小或最大的元素“浮”到顶端， 最终达到完全有序。

冒泡排序有两种优化方式。

一种是外层循环的优化，我们可以记录当前循环中是否发生了交换，如果没有发生交换，则说明该序列已经为有序序列了。 因此我们不需要再执行之后的外层循环，此时可以直接结束。

一种是内层循环的优化，我们可以记录当前循环中最后一次元素交换的位置，该位置以后的序列都是已排好的序列，因此下 一轮循环中无需再去比较。

优化后的冒泡排序，当排序序列为已排序序列时，为最好的时间复杂度为 O(n)。

冒泡排序的平均时间复杂度为 O(n²) ，最坏时间复杂度为 O(n²) ，空间复杂度为 O(1) ，是稳定排序。

## 4.2 选择排序 ##

选择排序的基本思想为每一趟从待排序的数据元素中选择最小（或最大）的一个元素作为首元素，直到所有元素排完为止。

在算法实现时，每一趟确定最小元素的时候会通过不断地比较交换来使得首位置为当前最小，交换是个比较耗时的操作。 其实我们很容易发现，在还未完全确定当前最小元素之前，这些交换都是无意义的。我们可以通过设置一个变量 min，每一次比较 仅存储较小元素的数组下标，当轮循环结束之后，那这个变量存储的就是当前最小元素的下标，此时再执行交换操作即可。 选择排序不管初始序列是否有序，时间复杂度都为 O(n²)。

选择排序的平均时间复杂度为 O(n²) ，最坏时间复杂度为 O(n²) ，空间复杂度为 O(1) ，不是稳定排序。

## 4.3 插入排序 ##

直接插入排序基本思想是每一步将一个待排序的记录，插入到前面已经排好序的有序序列中去，直到插完所有元素为止。

插入排序核心--扑克牌思想： 就想着自己在打扑克牌，接起来一张，放哪里无所谓，再接起来一张，比第一张小，放左边， 继续接，可能是中间数，就插在中间....依次

当排序序列为已排序序列时，为最好的时间复杂度 O(n)。

插入排序的平均时间复杂度为 O(n²) ，最坏时间复杂度为 O(n²) ，空间复杂度为 O(1) ，是稳定排序。

## 4.4 希尔排序 ##

希尔排序的基本思想是把数组按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的元素越来越多，当增量减至1时，整个数组恰被分成一组，算法便终止。

希尔排序是利用了插入排序对于已排序序列排序效果最好的特点，在一开始序列为无序序列时，将序列分为多个小的分组进行 基数排序，由于排序基数小，每次基数排序的效果较好，然后在逐步增大增量，将分组的大小增大，由于每一次都是基于上一 次排序后的结果，所以每一次都可以看做是一个基本排序的序列，所以能够最大化插入排序的优点。

简单来说就是，由于开始时每组只有很少整数，所以排序很快。之后每组含有的整数越来越多，但是由于这些数也越来越有序， 所以排序速度也很快。

希尔排序的时间复杂度根据选择的增量序列不同而不同，但总的来说时间复杂度是小于 O(n^2) 的。

插入排序是一个稳定排序，但是在希尔排序中，由于相同的元素可能在不同的分组中，所以可能会造成相同元素位置的变化， 所以希尔排序是一个不稳定的排序。

希尔排序的平均时间复杂度为 O(nlogn) ，最坏时间复杂度为 O(n^s) ，空间复杂度为 O(1) ，不是稳定排序。

## 4.5 归并排序 ##

归并排序是利用归并的思想实现的排序方法，该算法采用经典的分治策略。递归的将数组两两分开直到只包含一个元素，然后 将数组排序合并，最终合并为排序好的数组。

function MergeSort (arr, low, high) {
        const length = arr.length
        if (low === high) {
            return arr[low]
        }
        const mid = Math.floor((low + high)/2)
        MergeSort(arr, low, mid)
        MergeSort(arr, mid + 1, high)
        merge(arr, low, high)
        return arr
    
    }
    
    function merge (arr, low, high) {
        const mid = Math.floor((low + high)/2)
        let left = low
        let right = mid + 1
        const result = []
        while (left <= mid && right <= high) {
            if (arr[left] <= arr[right]) {
                result.push(arr[left++])
            } else {
                result.push(arr[right++])
            }
        }
        while (left <= mid) {
            result.push(arr[left++])
        }
        while (right <= high) {
            result.push(arr[right++])
        }
    
        arr.splice(low, high-low+1, ...result)
    }
    
    const test = [2, 34, 452,3,5, 785, 32, 345, 567, 322,5]
    
    console.log(MergeSort(test, 0, test.length - 1))

归并排序将整个排序序列看成一个二叉树进行分解，首先将树分解到每一个子节点，树的每一层都是一个归并排序的过程，每 一层归并的时间复杂度为 O(n)，因为整个树的高度为 lgn，所以归并排序的时间复杂度不管在什么情况下都为O(nlogn)。

归并排序的空间复杂度取决于递归的深度和用于归并时的临时数组，所以递归的深度为 logn，临时数组的大小为 n，所以归 并排序的空间复杂度为 O(n)。

归并排序的平均时间复杂度为 O(nlogn) ，最坏时间复杂度为 O(nlogn) ，空间复杂度为 O(n) ，是稳定排序。

## 4.6 快速排序 ##

快速排序的基本思想是通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据 都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

function quickSort(array){
    	if(array.length < 1){
        	return array;
        }
        let pivot = array[array.length - 1];
        let left = array.filter((v,i)=> v <=pivot && i != array.length - 1)
        let right = array.filter(v=> v > pivot)
        return [...quickSort(left),pivot,...quickSort(right)]
    }

*  Js中sort()对长度小于10的数组采用插入排序，对大于10的采用快速排序
 *  优化方法1：结合快排和插入排序，当排到集合长度小于某个数值时，采用插入排序等稳定的排序，优化效果；
 *  优化方法2：随机取基准值，因为每次取第一个或是最后一个，如果数组本身有序就会带来很多交换，因此随机取基准可以避免这个问题，由于Js的随机某种程度上是伪随机，可以采用随机三次来接近随机；
 *  优化方法三：取第一个、最后一个和中间值的中位数，来防止数组本身的顺序干扰；
 *  优化方法四：如果代码中有两次递归，可以将前一次递归改为循环，优化效率；
 *  优化方法五：将相同的数值聚集在一起，避免重复交换。

## 4.7 堆排序 ##

堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行 交换，此时末尾就为最大值。然后将剩余 n-1 个元素重新构造成一个堆，这样会得到 n 个元素的次小值。如此反复执行， 便能得到一个有序序列了。

建立堆的时间复杂度为 O(n)，排序循环的次数为 n-1，每次调整堆的时间复杂度为 O(logn)，因此堆排序的时间复杂度在 不管什么情况下都是 O(nlogn)。

堆排序的平均时间复杂度为 O(nlogn) ，最坏时间复杂度为 O(nlogn) ，空间复杂度为 O(1) ，不是稳定排序。

## 4.8 在大集合中找前K大的数 ##

这里以在一亿个数据里找出前10000大的数为例：

*  最容易想到的方法是将数据全部排序，然后在排序后的集合中进行查找，最快的排序算法的时间复杂度一般为O（nlogn），如快速排序。但是在32位的机器上，每个float类型占4个字节，1亿个浮点数就要占用400MB的存储空间，对于一些可用内存小于400M的计算机而言，很显然是不能一次将全部数据读入内存进行排序的。其实即使内存能够满足要求（我机器内存都是8GB），该方法也并不高效，因为题目的目的是寻找出最大的10000个数即可，而排序却是将所有的元素都排序了，做了很多的无用功。
 *  第二种方法为局部淘汰法，该方法与排序方法类似，用一个容器保存前10000个数，然后将剩余的所有数字——与容器内的最小数字相比，如果所有后续的元素都比容器内的10000个数还小，那么容器内这个10000个数就是最大10000个数。如果某一后续元素比容器内最小数字大，则删掉容器内最小元素，并将该元素插入容器，最后遍历完这1亿个数，得到的结果容器中保存的数即为最终结果了。此时的时间复杂度为O（n+m^2），其中m为容器的大小，即10000。
 *  第三种方法是分治法，将1亿个数据分成100份，每份100万个数据，找到每份数据中最大的10000个，最后在剩下的100\*10000个数据里面找出最大的10000个。如果100万数据选择足够理想，那么可以过滤掉1亿数据里面99%的数据。100万个数据里面查找最大的10000个数据的方法如下：用快速排序的方法，将数据分为2堆，如果大的那堆个数N大于10000个，继续对大堆快速排序一次分成2堆，如果大的那堆个数N大于10000个，继续对大堆快速排序一次分成2堆，如果大堆个数N小于10000个，就在小的那堆里面快速排序一次，找第10000-n大的数字；递归以上过程，就可以找到第1w大的数。参考上面的找出第1w大数字，就可以类似的方法找到前10000大数字了。此种方法需要每次的内存空间为10^6\*4=4MB，一共需要101次这样的比较。
 *  第四种方法采用最小堆。首先读入前10000个数来创建大小为10000的最小堆，建堆的时间复杂度为O（mlogm）（m为数组的大小即为10000），然后遍历后续的数字，并于堆顶（最小）数字进行比较。如果比最小的数小，则继续读取后续数字；如果比堆顶数字大，则替换堆顶元素并重新调整堆为最小堆。整个过程直至1亿个数全部遍历完为止。然后按照中序遍历的方式输出当前堆中的所有10000个数字。该算法的时间复杂度为O（nmlogm），空间复杂度是10000（常数）。
 *  第五种方法是Hash法。如果这1亿个书里面有很多重复的数，先通过Hash法，把这1亿个数字去重复，这样如果重复率很高的话，会减少很大的内存用量，从而缩小运算空间，然后通过分治法或最小堆法查找最大的10000个数。

## 4.9 老鼠试毒 ##

1000个杯子,均装有无色无味透明液体,其中1杯盛有毒性很强的溶液,其他均无毒。可以派老鼠试毒，老鼠可以喝很多杯子里的水，喝到有毒的会在12小时之后身亡，请问在12小时内找到有毒的杯子需要几只老鼠？

把1000瓶水编号：0~999

再转化成二进制数：0000000000～1111101000

每个二进制数都是唯一的，且与每个瓶子一一对应。

找到有毒的瓶子 == 找到有毒瓶子的二进制编号 == 确定有毒瓶子的二进制编号的每一位是0还是1。

问题转化成了：确定有毒瓶子的二进制编号的每一位是0还是1。

我们开始了：

每一个二进制编号都有10个位。

左数第一位的确定：把所有第一位为0的二进制数分为一组，让小鼠1喝，12个小时后小鼠1身亡，则说明有毒的瓶子的第一位为0，否则为1

左数第二位的确定：把所有第二位为0的二进制数分为一组，让小鼠2喝，12个小时后小鼠2身亡，则说明有毒的瓶子的第二位为0，否则为1

左数第三位的确定：把所有第三位为0的二进制数分为一组，让小鼠3喝，12个小时后小鼠3身亡，则说明有毒的瓶子的第三位为0，否则为1