[LeetCode] 1399. Count Largest Group JS

內容目錄 隱藏

題目

Count the digit sum for each integer in the range and find out the largest groups.

以 Example 1 為例，n=13，即 1~13，可以設想有一個 [1,2,3,4,5,6,7,8,9,10,11,12,13] 的陣列，需要將元素的每個位數相加，然後將相加後的數再次分組，一樣大小的分一組。

比如 10 就是 1+0 = 1, 因此 1 和 10 會分在一組 [1, 10]

11 就是 1+1 = 2, 因此 2 和 11 會分在一組 [2, 11]

以此類推能夠得到一個二維陣列：

[[1,10],[2,11],[3,12],[4,13],[5],[6],[7],[8],[9]]

最後需要得出最多元素的組別總共有幾個？

[1, 10], [2, 11], [3, 12], [4, 13] 都是 2 個元素，其他都是 1 個元素，所以最多元素就是 2，而元素數量為 2 的有 4 個，所以答案為 4

解題思路

首先將元素的每個位數相加
將相加後總和一樣的數分在一組，組成一個二維陣列
找出二維陣列中最長的陣列有多長
找出長度一致的陣列有幾個

程式碼

這是我最初的寫法：

/**
 * @param {number} n
 * @return {number}
 */
var countLargestGroup = function(n) {
    let groups = []
    let size = 1
    for (let i = 1; i <= n; i++) {
        let sum = i.toString().split('').reduce((acc,cur) => acc + Number(cur), 0)
        // 將相同總數的元素放在一起
        if (!groups[sum]) groups[sum] = [i]
        else groups[sum].push(i)
        // 紀錄最長的陣列有多長
      	size = Math.max(groups[sum].length, size)
    }
    // 找出相同長度的group總共有幾個
    const counts = groups.filter(group => group && group.length === size).length
    return counts
};

這樣寫應付easy題是沒什麼問題，但效能不佳。

其實根本不用儲存全部的group，可以改用 Map 優化一下：

/**
 * @param {number} n
 * @return {number}
 */
var countLargestGroup = function(n) {
    const groups = new Map()
    let maxSize = 0

    for (let i = 1; i <= n; i++) {
        let sum = 0, x = i
        while (x) {
            sum += x % 10
            x = (x / 10) | 0
        }
        const newCount = (groups.get(sum) || 0) + 1
        groups.set(sum, newCount)
        if (newCount > maxSize) maxSize = newCount
    }

    let result = 0
    for (const counts of groups.values()) {
        if (counts === maxSize) result++
    }

    return result
};

瀏覽量: 8