iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 12
3

大家一定會寫的題目,因為是第一題 XD。今天會知道選擇適合資料結構解決問題是非常重要的,但要如何選擇? 前提就是要對資料結構概念跟寫法需要有一定熟悉程度


1. Two Sum

題目連結在此

/*
Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1]
*/

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */

var twoSum = function(nums, target) {
  
};

Think

極限值/特殊狀況

  • 負數
  • 可能會有同樣的值
  • nums.length < 2,根本無法相加。(但題目說一定會有結果所以這個可以忽略)

哪種資料結構解

  • 第一直覺會想到 Array

大概會怎麼解

  • i = 0 時, i[0] = 2, 所以我們要找的就是 9 - 2,所以我想要 indexOf( 9 - 2),看看有沒有。
  • 都找不到的話 i++,再重覆以上

用程式實踐

var twoSum = function(nums, target) {
    const len = nums.length;
    for(let i = 0; i< len; i++ ){
        var ind = nums.indexOf(target - nums[i]);
        if(ind !== -1 && i !== ind){
            return [i, ind];
        }
    }

};

用這個方法時間複雜度大於 Big (n²),因為 for 一次,indexOf 基本上也是再遍歷一次。難怪 Runtime: faster than 18.49% of JavaScript online submissions for Two Sum.

再想想看有沒有更好作法

哪種資料結構解

  • 我們其實是想要做 "Search" 所以 Map 會是更好做法。因為 Map 在尋找跟增加效能都比 Array 好

大概會怎麼解

其實概念跟之前大同小異,只是不同語法,效能就差很多。

用程式實踐

var twoSum = function(nums, target) {
    const m = new Map();
    let result;
    nums.forEach( (item, index) => {
        let indValue = target - item;
        if (m.has(indValue)) {
            result = [m.get(indValue), index];
        }
        m.set(item, index);
    })
    return result;
};

Runtime: 52 ms, faster than 92.70% of JavaScript online submissions for Two Sum.
分數從 18 瞬間到 92,所以說選擇適合資料結構解決問題是非常重要的


上一篇
Map vs. Object
下一篇
堆疊 Stack
系列文
前端工程師用 javaScript 學演算法32

1 則留言

1
miniGhost
iT邦新手 5 級 ‧ 2020-03-08 22:19:17

這個例子中,使用 Map 的效率感覺明顯會比使用 Array 快上許多,但因為 Map.prototype.hasMap.prototype.get 在時間複雜度上都還是 Big O(n) 的操作。如果跟使用 Object 當作映射用的 mapping 表似乎又會比 Map 快一點!?直接用 Object 的 key 取的資料的時間複雜度應該為 Big O(1)?

以下是我在 Leetcode 上的測試:
https://ithelp.ithome.com.tw/upload/images/20200308/20120484aeWUNMRpeI.png

第三個是使用 hannahpun 大大提供的 Map 解,另外兩個是都是使用 Object 去存放對應的資料並在需要時取出使用,差別在於第一種(如下)是使用 typeof map[indValue] !== 'undefined' 而第二種在判斷時是使用 Object.prototype.hasOwnProperty 去判斷鍵值是否存在:

var twoSum = function(nums, target) {
    const map = {}
    let result
    nums.forEach((item, index) => {
        let indValue = target - item;
        if(typeof map[indValue] !== 'undefined') {
            result = [map[indValue], index]
        }
        map[item] = index
    })
    return result
}

不過測試數次過後,感覺上面給的時間真的只能當參考,每次都不一樣。就算同樣的 code 都可以在71.41% - 98.10% 之間來回了

我要留言

立即登入留言