一篇帶給你Web前端算法面試題
時(shí)間復(fù)雜度分析
當(dāng)問(wèn)題規(guī)模數(shù)據(jù)大量增加時(shí)，重復(fù)執(zhí)行的次數(shù)也必定會(huì)增加，那么我們就有必要關(guān)心執(zhí)行次數(shù)是以什么樣的數(shù)量級(jí)增加，這也是分析時(shí)間復(fù)雜度的意義，是一個(gè)非常重要衡量算法好快的事前估算的方法
常見的時(shí)間復(fù)雜度：
- O(1)：常數(shù)階的復(fù)雜度，這種復(fù)雜度無(wú)論數(shù)據(jù)規(guī)模如何增長(zhǎng)，計(jì)算時(shí)間是不變的。
const increment = n => n++
- O(n)：線性復(fù)雜度，線性增長(zhǎng)。
// 最典型的例子就是線性查找
const linearSearch = (arr,target) = {
for (let i = 0;i<arr.length;i++){
if(arr[i] === target) return 1;
}
return -1;
}
- O(logn)：對(duì)數(shù)復(fù)雜度，隨著問(wèn)題規(guī)模的增長(zhǎng)，計(jì)算時(shí)間會(huì)對(duì)數(shù)級(jí)增長(zhǎng)，典型的例子是歸并查找。
- O(nlogn)：線性對(duì)數(shù)復(fù)雜度，計(jì)算時(shí)間隨數(shù)據(jù)規(guī)模呈線性對(duì)數(shù)級(jí)增長(zhǎng)，典型的例子是歸并排序。
- O(n^2)：平方級(jí)復(fù)雜度，典型就是雙層循環(huán)的時(shí)候，代表應(yīng)用是冒泡排序算法。
常見的排序算法
常見的排序算法這里總結(jié)四種最具代表性的：
冒泡排序
冒泡排序是一種簡(jiǎn)單的排序算法，它需要重復(fù)的走訪序列，一次只比較兩個(gè)數(shù)據(jù)，如果順序錯(cuò)誤則交換這兩個(gè)數(shù)據(jù)，直到?jīng)]有在需要交換的數(shù)據(jù)，走訪結(jié)束，具體算法描述如下：
比較相鄰元素，如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)依次走訪執(zhí)行第一步，那么第一趟后，最后的元素應(yīng)該是最大的數(shù)重復(fù)走訪，直到排序完成。
const bubbleSort = arr => {
console.time('bubbleSort耗時(shí)');
let len = arr.length;
for(let i = 0;i<len;i++){
for(let j = 0;j<len-i-1;j++){
if(arr[j]>arr[j+1]){
[arr[j],arr[j+1]] = [arr[j+1],arr[j]]
}
}
}
console.timeEnd('bubbleSort耗時(shí)');
return arr
}
冒泡排序改進(jìn)方案：
方案一：設(shè)置一個(gè)標(biāo)記變量pos，用來(lái)記錄每次走訪的最后一次進(jìn)行交換的位置，那么下次走訪之后的序列便可以不再訪問(wèn)。
const bubbleSort_pos = arr => {
console.time('bubbleSort_pos耗時(shí)')
let i = arr.length - 1;
while(i > 0){
let pos = 0;
for(var j=0;j<i;j++){
if(arr[j]>arr[j+1]){
pos = j;
[arr[j],arr[j+1]] = [arr[j+1],arr[j]];
}
}
i = pos;
}
console.timeEnd('bubbleSort_pos耗時(shí)')
return arr;
}
方案二：傳統(tǒng)冒泡一趟只能找到一個(gè)最大或者最小值，我們可以考慮在利用每趟排序過(guò)程中進(jìn)行正向和反向冒泡，一次可以得到一個(gè)最大值和最小值，從而使排序趟數(shù)幾乎減少一半。
const bubbleSort_ovonic = arr => {
console.time('bubbleSort_ovonic耗時(shí)')
let low = 0;
let height = arr.length -1;
let tmp,j;
while(low < height){
for(j=low;j<height;++j){ // 正向冒泡，找到最大值
if(arr[j] > arr[j+1]){
[arr[j],arr[j+1]] = [arr[j+1],arr[j]];
}
}
--height;
for(j=height;j>low;--j){ // 反向冒泡，找到最小值
if(arr[j] < arr[j-1]){
[arr[j-1],arr[j]] = [arr[j],arr[j-1]]
}
}
++low;
}
console.timeEnd('bubbleSort_ovonic耗時(shí)')
return arr;
}
以上提供兩種改進(jìn)冒泡的思路，耗時(shí)在這只是進(jìn)行粗略對(duì)比，并不完全確定好壞，相比之下改進(jìn)后的冒泡時(shí)間復(fù)雜度更低，下圖實(shí)例展示結(jié)果耗時(shí)更短。
快速排序
快速排序是分治策略的經(jīng)典實(shí)現(xiàn)，也是對(duì)冒泡排序的改進(jìn)，出現(xiàn)頻率較高，基本思路是經(jīng)過(guò)一趟排序，把數(shù)據(jù)分割成獨(dú)立的兩部分，其中一部分?jǐn)?shù)據(jù)要比另一部分都小，然后按此方法繼續(xù)排序，以達(dá)到整個(gè)序列有序，具體算法描述如下：
從數(shù)組中挑出一個(gè)元素作為"基準(zhǔn)"分區(qū)：所有比基準(zhǔn)小的值放前面，而比基準(zhǔn)大的值放后面，基準(zhǔn)處于數(shù)列中間位置按照此方法依次排序(遞歸)，以達(dá)到序列有序。
// 遞歸方法的其中一種形式
const quickSort = (arr) => {
if(arr.length <= 1){ return arr };
let pivotIndex = Math.floor(arr.length/2);
let pivot = arr.splice(pivotIndex,1)[0]; // 確定基準(zhǔn)
let left = [] , right = [];
for(let i = 0;i<arr.length;i++){
if(arr[i]<pivot){
left.push(arr[i]);
}else{
right.push(arr[i]);
}
}
return quickSort(left).concat([pivot],quickSort(right));
}
希爾排序
第一個(gè)突破O(n^2)的排序算法;是簡(jiǎn)單插入排序的改進(jìn)版;與插入排序的不同點(diǎn)在于，它會(huì)優(yōu)先比較距離較遠(yuǎn)的元素。希爾排序又叫做增量縮小排序，核心在于間隔序列的設(shè)定，既可以提前設(shè)定好間隔序列，也可以動(dòng)態(tài)的定義間隔序列，后者是《算法(第四版)》中提出的，實(shí)現(xiàn)如下：
選擇一個(gè)增量序列t1,t2...tk，其中ti>tj，tk=1按增量序列個(gè)數(shù)k，對(duì)序列進(jìn)行k趟排序每趟排序根據(jù)對(duì)應(yīng)的增量ti，將待排序列分割成長(zhǎng)度為m的若干子序列，然后分別對(duì)各子表進(jìn)行直接插入排序。僅當(dāng)增量因子為1時(shí)，整個(gè)序列作為一個(gè)表來(lái)處理，表長(zhǎng)度即為整個(gè)序列的長(zhǎng)度。
const shellSort = arr => {
console.time('shellSort耗時(shí)')
let len = arr.length,
gap = 1,
temp;
while(gap < len/5){ gap = gap*5+1 } // 動(dòng)態(tài)定義間隔序列
for(gap; gap > 0; gap = Math.floor(gap/5)){
for(let i = gap;i<len;i++){
temp = arr[i];
for(var j=i-gap; j>=0&&arr[j]>temp; j-=gap){
arr[j+gap] = arr[j];
}
arr[j+gap] = temp;
}
}
console.timeEnd('shellSort耗時(shí)');
return arr;
}
歸并排序
歸并排序不受輸入數(shù)據(jù)的影響，時(shí)間復(fù)雜度始終都是O(nlogn)，但代價(jià)是需要額外的內(nèi)存空間。歸并排序也是分治法的經(jīng)典體現(xiàn)，先使子序列有序，再使子序列段間有序，若將兩個(gè)有序表合并成一個(gè)有序表，稱為2-路歸并。實(shí)現(xiàn)如下：
將長(zhǎng)度為n的序列，分成兩個(gè)長(zhǎng)度為n/2的子序列對(duì)這兩個(gè)子序列分別采用歸并排序?qū)蓚€(gè)排序好的子序列合并成最終排序序列。
const merge = (left,right) => {
let result = [];
while(left.length && right.length){
if(left[0] <= right[0]){
result.push(left.shift());
}else{
result.push(right.shift());
}
}
while(left.length)
result.push(left.shift());
while(right.length)
result.push(right.shift());
return result;
}
const mergeSort = arr => {
let len = arr.length;
if(len < 2) return arr;
let middle = Math.floor(len / 2),
left = arr.slice(0,middle),
right = arr.slice(middle);
return merge(mergeSort(left),mergeSort(right));
}
常見的查找算法
線性查找
線性查找較簡(jiǎn)單，只需要簡(jiǎn)單遍歷即可。
const linearSearch = (arr,target) => {
for(let i =0;i<arr.length;i++){
if(arr[i] === target) return i
}
return -1
}
時(shí)間復(fù)雜度：最佳情況O(n)，最差情況O(n)，平均情況O(n)
二分查找法
也叫作折半查找，要求查找表的數(shù)據(jù)實(shí)現(xiàn)線性結(jié)構(gòu)存儲(chǔ)，還要求查找表中的順序是有序的
實(shí)現(xiàn)思路如下：
首先設(shè)兩個(gè)指針，low表示最低索引，height表示最高索引然后取中間位置索引，判斷middle處的值是否是要查找的數(shù)字，是則查找結(jié)束;比所求值較小就把low設(shè)為middle+1，較大則把height設(shè)為middle-1然后到新分區(qū)繼續(xù)查找，直到找到或者low>height找不到要查找的值結(jié)束。
const binarySearch = (arr,target) => {
let height = arr.length - 1;
let low = 0;
while(low <= height){
let middle = Math.floor((low+height)/2)
if(target < arr[middle]){
height = middle - 1
}else if(target > arr[middle]){
low = middle + 1
}else{
return middle
}
}
return -1
}
時(shí)間復(fù)雜度分析：最佳情況O(logn)，最差情況O(logn)，平均情況O(logn)。
參考：damonare。
二叉樹的遍歷方式
二叉樹遍歷有四種方式：先序遍歷，中序遍歷，后序遍歷，層序遍歷。
前序遍歷：先訪問(wèn)根節(jié)點(diǎn)，然后前序遍歷左子樹，再前序遍歷右子樹。
中序遍歷：先中序遍歷左子樹，然后訪問(wèn)根節(jié)點(diǎn)，最后遍歷右子樹。
后序遍歷：從左到右，先葉子后結(jié)點(diǎn)的方式遍歷訪問(wèn)左子樹，最后訪問(wèn)根節(jié)點(diǎn)。
層序遍歷：從根結(jié)點(diǎn)從上往下逐層遍歷，在同一層，按從左到右的順序?qū)Y(jié)點(diǎn)逐個(gè)訪問(wèn)。
實(shí)現(xiàn)二叉樹的層序遍歷
有兩種通用的遍歷樹的策略：
深度優(yōu)先遍歷(DFC)
正如名字一樣，深度優(yōu)先遍歷采用深度作為優(yōu)先級(jí)，從某個(gè)確定的葉子，然后再返回根到另個(gè)分支，有細(xì)分為先序遍歷，中序遍歷和后序遍歷
廣度優(yōu)先遍歷(BFC)
廣度優(yōu)先按照高度順序一層一層訪問(wèn)整棵樹，高層次的結(jié)點(diǎn)會(huì)比低層的結(jié)點(diǎn)先訪問(wèn)到
// 通過(guò)迭代方式實(shí)現(xiàn)
const levelOrder = function(root) {
const res = [];
const stack = [{ index: 0, node: root }];
while (stack.length > 0) {
const { index, node } = stack.pop();
if (!node) continue;
res[index] = res[index] ? [...res[index], node.val] : [node.val];
stack.push({ index: index + 1, node: node.right });
stack.push({ index: index + 1, node: node.left });
}
return res;
};
