題目資訊

題目編號: 2094
題目連結: Finding 3-Digit Even Numbers
主題: Array, Hash Table, Sorting, Enumeration

題目敘述

你有一個整數陣列 digits，其中每個元素都是一個數字。這個陣列可能含有重複的元素。

你需要找到所有符合以下要求的唯一整數：

整數由 digits 中任意三個元素串接而成。
整數沒有前導零。
整數是偶數。

例如，如果給定的 digits 是 [1, 2, 3]，則整數 132 和 312 符合要求。

返回一個排序後的唯一整數陣列。

範例 1:

輸入: digits = [2,1,3,0]
輸出: [102,120,130,132,210,230,302,310,312,320]
解釋: 所有符合要求的可能整數都在輸出陣列中。
注意，沒有奇數或有前導零的整數。

範例 2:

輸入: digits = [2,2,8,8,2]
輸出: [222,228,282,288,822,828,882]
解釋: 同一位數可以按照其在 digits 中出現的次數使用多次。
在這個例子中，數字 8 每次在 288、828 和 882 中都使用了兩次。

範例 3:

輸入: digits = [3,7,5]
輸出: []
解釋: 無法使用給定的數字形成偶數整數。

約束條件:

$3 \leq \text{digits.length} \leq 100$
$0 \leq \text{digits}[i] \leq 9$

直覺

這個問題要求使用給定的數字生成所有唯一的三位數偶數。這涉及到一種組合方法，其中我們應該系統地考慮數字的所有可能排列，以形成符合條件的有效數字：三位數、偶數，且沒有前導零。在給定的限制條件下，直接檢查所有可能的三位數字是可行的。

解法

提供的解法使用一種系統化的方法來檢查在從100到998範圍內的每一個可能的三位數偶數。該演算法構建這些數字並根據以下步驟驗證它們是否可以使用輸入數組中的數字來形成：

數字頻率計數：
- 首先，我們建立一個頻率數組 digitCount，該數組統計輸入數組 digits 中每個數字（0-9）的出現次數。這有助於快速驗證形成數字所需的數字是否可用。
迭代可能的數字：
- 演算法遍歷從100到998的所有可能的三位數偶數，每次增量為2（確保這些數字為偶數）。
抽取每個候選數字的數字：
- 對於每個候選數字，提取其百位數、十位數和個位數。這是通過算術運算完成的：
  - 百位數：$\text{number} / 100$
  - 十位數：$(\text{number} / 10) % 10$
  - 個位數：$\text{number} % 10$
用數字頻率檢查可形成性：
- 對於提取的每個數字，維護一個頻率計數（needed）以確定形成當前候選數所需的每個數字的次數。
- 將此所需頻率與從輸入獲得的可用頻率（digitCount）進行比較。如果任何所需數字的計數超過了可用的計數，則無法形成該數字。
收集有效數字：
- 如果一個候選數字可以用給定的數字可用性來形成（即 canFormNumber 仍為真），則將其添加到結果列表中。
返回結果：
- 結果向量，包括所有有效的、唯一的和排序的偶數，作為最終輸出返回。

在問題的限制條件下，這種暴力方法是有效的，因為它涉及到可管理的數字範圍（450個可能的偶數），並利用直接頻率匹配來確認有效的構造。

程式碼

C++

class Solution {
public:
    vector<int> findEvenNumbers(vector<int>& digits) {
        // 頻率陣列，用來計數 `digits` 中每個從 0 到 9 的數字
        vector<int> digitCount(10, 0);
        for (int digit : digits) {
            ++digitCount[digit];
        }

        vector<int> result;
        
        // 遍歷所有從 100 到 998 的三位偶數
        for (int number = 100; number <= 998; number += 2) {
            // 提取百位、十位和個位數字
            int hundreds = number / 100;
            int tens = (number / 10) % 10;
            int units = number % 10;

            // 當前數字的頻率陣列
            vector<int> needed(10, 0);
            ++needed[hundreds];
            ++needed[tens];
            ++needed[units];

            // 檢查當前數字能否用可用的數字組成
            bool canFormNumber = true;
            if (needed[hundreds] > digitCount[hundreds] ||
                needed[tens] > digitCount[tens] ||
                needed[units] > digitCount[units]) {
                canFormNumber = false;
            }

            // 如果可以組成該數字，將其加入結果向量
            if (canFormNumber) {
                result.push_back(number);
            }
        }

        return result;
    }
};

Python

class Solution:
    def findEvenNumbers(self, digits: List[int]) -> List[int]:
        # 頻率陣列，用來計算在 `digits` 中每個數字從 0 到 9 出現的次數
        digitCount = [0] * 10
        for digit in digits:
            digitCount[digit] += 1

        result = []
        
        # 遍歷所有從 100 到 998 的 3 位數偶數
        for number in range(100, 999, 2):
            # 提取百位數、十位數和個位數的數字
            hundreds = number // 100
            tens = (number // 10) % 10
            units = number % 10

            # 當前數字的頻率陣列
            needed = [0] * 10
            needed[hundreds] += 1
            needed[tens] += 1
            needed[units] += 1

            # 檢查當前數字是否可以用可用數字形成
            canFormNumber = True
            if (needed[hundreds] > digitCount[hundreds] or
                needed[tens] > digitCount[tens] or
                needed[units] > digitCount[units]):
                canFormNumber = False

            # 如果可以形成該數字，則將其添加到結果向量中
            if canFormNumber:
                result.append(number)

        return result

複雜度分析

時間複雜度: $O(1)$
該演算法遍歷了從 100 到 998 的所有三位數偶數，這是一個恆定次數的操作（450 次迭代）。在每次迭代中，它執行固定數量的工作，包括提取數字和檢查條件，因此在給定限制條件下，時間複雜度為 $O(1)$。
空間複雜度: $O(1)$
儘管受到限制條件的影響，該演算法維持了一個固定大小的頻率數組，用於數字計數和所需數字計數。所使用的空間並不會隨著輸入大小縮放，因此空間複雜度為 $O(1)$。

CS Note
En

Leetcode 2094. Finding 3-Digit Even Numbers

題目資訊

題目敘述

直覺

解法

程式碼

C++

Python

複雜度分析