「面試指南」JS數組Array常用演算法,Array演算法的一般解答思路

  • 2020 年 3 月 30 日
  • 筆記

先看一道面試題

在 LeetCode 中有這麼一道簡單的數組演算法題：

// 給定一個整數數組 nums 和一個目標值 target，  // 請你在該數組中找出和為目標值的那兩個整數，並返回他們的數組下標。  // 你可以假設每種輸入只會對應一個答案。  // 但是，你不能重複利用這個數組中同樣的元素。  // 示例:  //    給定 nums = [2, 7, 11, 15], target = 9;  //    因為 nums[0] + nums[1] = 2 + 7 = 9,  //    所以返回 [0, 1]。

對於上述的面試題，對於我們前端開發，不同的解法，有著不同的技術水準。

那麼到底有幾種常用解法？實踐並匯總了以下幾種方法：

  • 暴力雙 for 循環解法；
  • 單循環 indexOf 優化；
  • 單循環 obj 優化；
  • 單循環 map 優化；
  • 單循環尾遞歸優化；

暴力雙 for 循環破解

// 兩層循環判斷，找出當前元素cur與target-cur的，滿足放入result結果中  function twoSum(nums, target) {    for (let i = 0; i < nums.length; i++) {      const cur = nums[i];        for (let j = 0; j < nums.length; j++) {        const others = nums[j];        // 因為是不可以重複利用同樣的元素，所以i!==j;        if (others == target - cur && i !== j) {          // 因為是我們只找出一個結果，所以我們找到後，直接返回結果          return [i, j];        }      }    }    // 如果未找到，返回[]    return [];  }    // 測試結果  let result = twoSum([2, 7, 11, 15], 9);  console.log(result); // [0,1]  2,7 滿足結果，所以返回其下標[0,1]

時間複雜度：O(n^2),可能看似感覺還不錯，但是執行時間長，記憶體佔用也不小，當 nums 數組足夠大時，它的性能瓶頸就會體現出來。

leetCood 測試結果：

csjg

單循環 indexOf 優化；

// 單循環判斷，找出當前元素cur，與target-cur是否相等，滿足放入result結果中  function twoSum(nums, target) {    for (let i = 0; i < nums.length; i++) {      let cur = nums[i],        others = target - cur, // 期望目標值        others_index = nums.indexOf(others);        // 判斷期望目標值是否在nums中，因為不能是它本身，要校驗兩個下標不能相等      if (others_index > -1 && i !== others_index) {        // 因為是我們只找出一個結果，所以我們找到後，直接返回結果        return [i, others_index];      }    }    // 如果未找到，返回[]    return [];  }    // 測試結果  let result = twoSum([2, 7, 11, 15], 9);  console.log(result); // [0,1]  2,7 滿足結果，所以返回其下標[0,1]

時間複雜度：O(n^2),因為 indexOf()方法的時間複雜度為 O(n),所以和上述暴力破解只是寫法上區別了。執行時間，記憶體佔用依然存在可優化的空間。

leetCood 測試結果：

測試結果

單循環 obj 優化：

使用 obj，邊存邊比較目標差值是否在 obj 中。如果存在，直接返回下標，不存在繼續邊存邊比，直到結束循環；

function twoSum(nums, target) {    let obj = {};      for (let i = 0; i < nums.length; i++) {      if (obj[target - nums[i]] >= 0) {        return [obj[target - nums[i]], i];      }      obj[nums[i]] = i;    }    return [];  }  // 測試結果  let result = twoSum([2, 7, 11, 15], 9);  console.log(result); // [0,1]  2,7 滿足結果，所以返回其下標[0,1]

時間複雜度：O(n),由於對象鍵值對 key-value 的優越性，對於作為查找類的演算法很有優勢。時間複雜度降為原有的一倍，性能會好一些。

leetCood 測試結果(較上優化了 90ms 左右)：

測試結果

單循環 map 優化：

上述我們使用了一個對象作為查找的依據，同樣的我們可以根據 map 替換，來破解。

function twoSum(nums, target) {    let map = new Map();      // 遍歷nums 放入 map中    for (let i = 0; i < nums.length; i++) {      let value = nums[i];        map.set(value, i);    }      for (let j = 0; j < nums.length - 1; j++) {      if (map.has(target - nums[j]) && map.get(target - nums[j]) != j) {        return [j, map.get(target - nums[j])];      }    }    // 不符合，返回空數組    return [];  }  // 測試結果  let result = twoSum([2, 7, 11, 15], 9);  console.log(result); // [0,1]  2,7 滿足結果，所以返回其下標[0,1]

時間複雜度：O(2n),第一次循環時間度 n,第二次為 n*1，故為 O(2n), 由於 map 的特殊數據結構，故作為查找類的演算法，相比 obj 具有絕對優勢。

leetCood 測試結果(較上再次優化了 近 30ms)：

測試結果

obj 尾遞歸優化；

我們對於上面單循環 obj 做下改造，利用尾遞歸的方式破解：

var twoSum = function(nums, target, i = 0, objs = {}) {    const obj = objs; //存在期望數字;    // 判斷obj中是否    if (obj[target - nums[i]] >= 0) {      // 存在直接返回兩值的下標;      return [obj[target - nums[i]], i];    } else {      // 不存在，存入obj      obj[nums[i]] = i;      // 遞歸繼續查找      if (i < nums.length - 1) {        // i 自增        i++;        return twoSum(nums, target, i, obj);      } else {        // 遞歸結束，未查詢到結果        return [];      }    }  };

時間複雜度：O(n),假設我們查找到,則遞歸的次數應該是最多的為 n，所以時間複雜度 O(n);
遞歸相比於 for 循環是一種更近層次的查找，在樹結構數據、多維數組中我們常用遞歸思想來處理數據。

leetCood 測試結果(結果為 52ms)，多次執行測試大都在 60ms 上下，說明了遞歸思想的優勢：

測試結果

map 尾遞歸優化破解；

我們同時對單循環 map 的也是用遞歸，看看會發生什麼結果？

var twoSum = function(nums, target, i = 0, maps = new Map()) {    const map = maps;      // 判斷obj中是否    if (map.has(target - nums[i])) {      // 存在直接返回兩值的下標;      return [map.has(target - nums[i]), i];    } else {      // 不存在，存入obj      map.set([nums[i]], i);      // 遞歸繼續查找      if (i < nums.length - 1) {        // i 自增        i++;        return twoSum(nums, target, i, map);      } else {        // 遞歸結束，未查詢到結果        return [];      }    }  };

時間複雜度：O(n),假設我們查找到,則遞歸的次數為 n，所以時間複雜度也為 O(n);

leetCood 測試結果(最快結果為 44ms)，多次執行測試大都在 60ms 上下，與上一個性能相似：

測試結果

當然，測試結果只是一個參考可能不太準確，不過通過多次測試也是可以看出他們之間的差距的。

總結：

以上我們使用了暴力破解、單循環 obj、單循環 map、obj 尾遞歸、map 尾遞歸做了對比。

一般對於數組的演算法，幾乎都可以使用上次思路來解決，當然我們要知道衡量演算法指標時間複雜度 O()、空間複雜度 S()。

空間複雜度：演算法的空間複雜度通過計算演算法所需的存儲空間實現，演算法的空間複雜度的計算公式記作：S(n)=O(f(n))，其中，n 為問題的規模，f(n)為語句關於 n 所佔存儲空間的函數。

通常，我們都是用「時間複雜度」來指運行時間的需求，是用「空間複雜度」指空間需求。

當直接要讓我們求「複雜度」時，通常指的是時間複雜度。不過，在一定程度上我們也要考慮演算法所需存儲空間。

在面試中與實際工作中，簡單數組演算法的幾點經驗之談：

數組去重：使用單循環，結合 obj 或 map 做中間輔助判斷；
數組扁平化：使用遞歸；

樹結構的查找與處理：單循環使用 obj/map 做中間輔助判斷，同時結合遞歸思想；

數組的特定重組：除了上述思想外，可能要結合數組常用方法：indexOf(),map(),forEach()或數組高階函數 filter(),reduce(),sort(),every(),some()等。本文只是拋出一個演算法的思路，不再做長篇大論的演示。

// 遞歸思路  // 最簡遞歸:for循環形式  function recursive_simple(array) {    for (let i = 0; i < array.length; i++) {      const item = array[i];        // 進入遞歸ifEntry:遞歸條件,subArray:遞歸參數      if (ifEntry) {        // do something        recursive_simple(subArray);      } else {        // 跳出遞歸        // do something      }    }  }    // 尾遞歸  function recursive_tail(array, i = array.length - 1, others) {    const other = others;    //do something      // 進入遞歸，others:其他參數,可以obj、map等一些中間臨時變數    if (i > 0) {      // do something      console.log(i, array[i]);        i--;      // 遞歸調用      return recursive_tail(array, i, others);    }  }

涉及方法：

indexOf():檢測 searchString 在 string、array 是否存在，不過時間複雜度 O(n);

map:數組的遍歷，返回新的數組，需要手動 return 當前 item;對於數組中對象的 key-value 改寫比較適合，時間複雜度 O(n);

forEach:改寫當前數組，不需要 return，對於直接改寫某個數組比較合適；

filter：過濾函數，對於過濾數組中符合某個條件的子項比較合適；

reduce:接收一個函數作為累加器(accumulator)，返回具體數值，對於需要對數組某些子項操作的比較合適，比如求和，斐波那契數列等的處理,
reduce(function(total, currentValue, currentIndex, arr), initialValue);

sort:適合數組中，複雜比較關係的，一般用於排序用途；

every：數組迭代方法，對數組中每一項運行給定函數，如果該函數對每一項返回 true,則返回 true;

some:數組迭代方法，對數組中每一項運行給定函數，如果該函數對任一項返回 true,則返回 true，與 every 有區別，如其名：every:每一項，some:任一項;

微信公眾號：前端開發那些事兒，歡迎關注！

前端開發那些事兒

VirMach 便宜 VPS

QNews

QNews