題目
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
};
