題目資訊

題目編號: 1399
題目連結: Count Largest Group
主題: Hash Table, Math

題目敘述

你得到一個整數 $n$。

從 $1$ 到 $n$ 的每個數字都根據其數位和進行分組。

返回具有最大大小的組的數量。

例子 1:

輸入: n = 13
輸出: 4
解釋: 總共有 9 個組，根據從 1 到 13 的數字的數位和進行分組：
[1,10], [2,11], [3,12], [4,13], [5], [6], [7], [8], [9]。
有 4 個組具有最大大小。

例子 2:

輸入: n = 2
輸出: 2
解釋: 有 2 個大小為 1 的組 [1], [2]。

限制條件:

$1 \leq n \leq 10^4$

直覺

這個問題涉及將數字根據其數字和進行分組，並識別出最大組的數量。起初，這似乎很複雜，因為需要計算每個數字的數字和直到 $n$。然而，通過系統化的方法，這個問題就變得簡單了。藉由計算數字和來進行分組，我們可以輕鬆追蹤每個組的頻率並確定哪個組最大。

解法

為了解決這個問題，第一步是計算從 $1$ 到 $n$ 的每個數字的數字和。我們通過一個輔助函數 sumOfDigits 來達成這一目的，該函數遍歷每個數字的位數，將其添加到累積和中，然後通過整數除法移動到下一個數位。

數字和計算：對於從 $1$ 到 $n$ 的每個數字，使用 sumOfDigits 函數計算其數字和。該函數通過反覆提取數字的最後一位（使用取模運算 % 10），然後移除該數位（使用整數除法 / 10）來處理一個數字。
根據數字和分組：使用一個映射（digitSumCount）來統計每個數字和的頻率。鍵是數字和，值是具有該數字和的數字的頻率。
確定最大組的大小：遍歷該映射以找到出現頻率最高的組大小。將 largestSize 初始化為零，在發現更大的組大小時進行更新。同時，維持一個計數 numberOfLargestGroups，以記錄擁有此最大大小的組數量。
計算結果：在遍歷映射後，numberOfLargestGroups 將包含擁有最大大小的組的數量，這就是所需的輸出。

這種方法有效地分組數字並追蹤每組的大小，允許在沒有不必要計算的情況下確定有多少組具有最大大小。

程式碼

C++

class Solution {
private:
    // 助手函式，用於計算給定數字的數字和。
    int sumOfDigits(int num) {
        int sum = 0;
        while (num > 0) {
            sum += num % 10;  // 將最後一位數字加到總和中。
            num /= 10;        // 移除最後一位數字。
        }
        return sum;
    }

public:
    // 主函式，用於計算最大大小的群組數目。
    int countLargestGroup(int n) {
        int largestSize = 0;  // 用於追蹤最大群組的大小。
        int numberOfLargestGroups = 0;  // 用於計算擁有最大大小的群組數目。
        map<int, int> digitSumCount;  // 映射，用於儲存每個數字和的頻率。

        // 計算每個數字的數字和並更新計數。
        for (int i = 1; i <= n; ++i) {
            int digitSum = sumOfDigits(i);
            digitSumCount[digitSum]++;
        }

        // 遍歷映射以找到最大群組的大小並計算它們。
        for (pair<int, int> group : digitSumCount) {
            if (group.second > largestSize) {
                largestSize = group.second;  // 更新最大的大小。
                numberOfLargestGroups = 1;   // 重新設定最大大小的計數。
            } else if (group.second == largestSize) {
                numberOfLargestGroups++;     // 如果找到另一個最大群組則增加計數。
            }
        }

        return numberOfLargestGroups;
    }
};

Python

class Solution:

    # 輔助函數來計算給定數字的數字之和。
    def sumOfDigits(self, num):
        total = 0
        while num > 0:
            total += num % 10  # 將最後一位數字加到總和。
            num //= 10         # 移除最後一位數字。
        return total

    # 主函數來計算擁有最大大小的群組數量。
    def countLargestGroup(self, n):
        largestSize = 0  # 追踪最大群組的大小。
        numberOfLargestGroups = 0  # 計算擁有最大大小的群組數量。
        
        digitSumCount = {}  # 字典來存儲每個數字之和的頻率。

        # 計算每個數字的數字之和並更新計數。
        for i in range(1, n + 1):
            digitSum = self.sumOfDigits(i)
            if digitSum in digitSumCount:
                digitSumCount[digitSum] += 1
            else:
                digitSumCount[digitSum] = 1

        # 遍歷字典以找到最大群組大小並計算它們。
        for count in digitSumCount.values():
            if count > largestSize:
                largestSize = count  # 更新最大大小。
                numberOfLargestGroups = 1  # 重置最大大小的計數。
            elif count == largestSize:
                numberOfLargestGroups += 1  # 如果找到另一個最大群組則增加計數。

        return numberOfLargestGroups

複雜度分析

時間複雜度: 函數 countLargestGroup 迭代從 $1$ 到 $n$ 的每個數字。對於每個數字，它使用 sumOfDigits 函數計算其數字和。對一個數字計算數字和的時間複雜度是 $O(\log_{10} m)$，其中 $m$ 是該數字。由於 $m$ 最多可以是 $n$，從 $1$ 到 $n$ 的所有數字的數字和的時間複雜度是 $O(n \log_{10} n)$。此外，迭代地圖以確定最大的組大小也需要線性時間，即 $O(k)$，其中 $k$ 是不同數字和的數量（對於大數字的和，最多為 $9 \times \log_{10} n$）。因此，總體時間複雜度是 $O(n \log n)$。
空間複雜度: 該函數使用一個映射來存儲數字和的頻率，這需要與不同數字和數量成正比的空間。數字 $n$ 的最大數字和是 $9 \times \log_{10} n$（因為每個數字最多是 9），所以地圖的大小最多是 $9 \times \log_{10} n$。因此，空間複雜度是 $O(\log n)$。

CS Note
En

Leetcode 1399. Count Largest Group

題目資訊

題目敘述

直覺

解法

程式碼

C++

Python

複雜度分析