題目資訊

• 題目編號: 1295
• 題目連結: Find Numbers with Even Number of Digits
• 主題: Array, Math

題目敘述

給定一個整數陣列 $nums$，返回其中包含偶數個數字的數量。

範例 1:

輸入: nums = [12,345,2,6,7896]
輸出: 2
解釋: 
12 包含 2 個數字（偶數個數字）。
345 包含 3 個數字（奇數個數字）。
2 包含 1 個數字（奇數個數字）。
6 包含 1 個數字（奇數個數字）。
7896 包含 4 個數字（偶數個數字）。
因此，只有 12 和 7896 包含偶數個數字。

範例 2:

輸入: nums = [555,901,482,1771]
輸出: 1
解釋: 
只有 1771 包含偶數個數字。

約束條件:

• $1 \leq nums.length \leq 500$
• $1 \leq nums[i] \leq 10^5$

直覺

這個問題要求我們確定在給定的數組中，擁有偶數位數的整數的數量。解決此問題的關鍵是準確計算數組中每個整數的位數。如果一個整數擁有偶數的位數，我們便增加計數。我們的第一個直覺是遍歷清單中的每一個整數並評估其位數。

解法

為了解決這個問題，我們實施以下方法：

1. 初始化計數器：首先，我們聲明一個變數 evenDigitCount 並將其初始化為零。此變數將儲存具有偶數位數的數字的數量。

2. 遍歷數組：我們遍歷數組 nums 中的每一個整數 num。

3. 計算位數：對於每個整數 num，我們確定它包含的位數。我們可以利用以 10 為底的對數函數 log10(num) 來計算，該函數返回位數減一。我們加上 1 顯示準確的位數，因此表達式 int(log10(num)) + 1 給出完整的位數。

4. 檢查位數的偶數性：接下來，我們檢查這个位數是否為偶數，方法是評估 numDigits % 2 == 0。如果此條件為真，則表示位數為偶數。

5. 增加計數器：如果 numDigits 是偶數，我們便增加 evenDigitCount。

6. 返回結果：在遍歷所有數字後，返回 evenDigitCount 的值，該值代表包含偶數位數的數字總數。

這個解決方案有效地遍歷每個數字，並通過對數來確定位數，確保我們在滿足約束條件的情況下，進行最佳的計算。

程式碼

C++

class Solution {
public:
    int findNumbers(vector<int>& nums) {
        int evenDigitCount = 0; // 初始化計數器以計算擁有偶數位數的數字
        
        for (int num : nums) {
            // 檢查位數是否為偶數。
            // log10(num) 得到位數減一的值。
            // 加上1使其成為確切的位數。
            // 如果結果是偶數，(numDigits % 2 == 0) 為真。
            int numDigits = int(log10(num)) + 1;
            if (numDigits % 2 == 0) {
                evenDigitCount++; // 若符合條件則增加計數
            }
        }
        
        return evenDigitCount; // 返回擁有偶數位數的數字總數
    }
};

Python

class Solution:
    def findNumbers(self, nums):
        evenDigitCount = 0  # 初始化計算擁有偶數數位的數字的計數器
        
        for num in nums:
            # 檢查數字的位數是否為偶數。
            # log10(num) 給予數字的位數減一。
            # 加 1 使其成為確切的位數。
            # 如果結果為偶數，(numDigits % 2 == 0) 成立。
            numDigits = int(log10(num)) + 1
            if numDigits % 2 == 0:
                evenDigitCount += 1  # 如果條件滿足，增加計數
        
        return evenDigitCount  # 返回擁有偶數位數的數字的總計數器

複雜度分析

• 時間複雜度: $O(n \cdot \log_{10}(k))$

  時間複雜度主要涉及迭代遍歷大小為 $n$ 的數組 nums 中的每個元素。對於每個數字，進行對數計算，特別是 $\log_{10}$，以確定數字中的位數。給定 $k$ 是 nums 中每個元素可能的最大值（$k = 10^5$），那麼確定數字中位數的複雜度為 $O(\log_{10}(k))$。因此，該算法的總時間複雜度為 $O(n \cdot \log_{10}(k))$。

• 空間複雜度: $O(1)$

  空間複雜度為常數，即 $O(1)$，因為該算法僅使用固定數量的額外記憶體，無論輸入大小如何。這包括存儲 evenDigitCount 整數和循環變量。空間使用不會隨輸入大小 $n$ 而變化。