2094. Finding 3-Digit Even Numbers

難度: Easy

類型: Array, Hash Table, Sorting, Enumberation,

CPP程式下載: 2094.cpp

前情題要:

從小到大排序列出可以用 nums 中的 digits 排出的三位數字

You are given an integer array digits, where each element is a digit. The array may contain duplicates.

You need to find all the unique integers that follow the given requirements:

• The integer consists of the concatenation of three elements from digits in any arbitrary order.
• The integer does not have leading zeros.
• The integer is even.

For example, if the given digits were [1, 2, 3], integers 132 and 312 follow the requirements.

Return a sorted array of the unique integers.

 

Example 1:

Input: digits = [2,1,3,0]
Output: [102,120,130,132,210,230,302,310,312,320]
Explanation: All the possible integers that follow the requirements are in the output array. 
Notice that there are no odd integers or integers with leading zeros.

Example 2:

Input: digits = [2,2,8,8,2]
Output: [222,228,282,288,822,828,882]
Explanation: The same digit can be used as many times as it appears in digits. 
In this example, the digit 8 is used twice each time in 288, 828, and 882. 

Example 3:

Input: digits = [3,7,5]
Output: []
Explanation: No even integers can be formed using the given digits.

 

Constraints:

• 3 <= digits.length <= 100
• 0 <= digits[i] <= 9

思考方式:

1. 記住每個數字重複發現的次數。

2. 從 100~999 檢查是否數字出現的數字是否可以組成。

複雜度思考:

Time Complexity: O( N+900 ) 

Space Complexity: O( x )

結果:

Runtime: 0 ms, Beats: 100%

Memory: 12.30 MB, Beats: 91.73%

Accepted

79 / 79 testcases passed

tendchen

submitted at May 12, 2025 10:58

Runtime

0ms

Beats100.00%

Analyze Complexity

Memory

12.30MB

Beats91.73%

Analyze Complexity

Code

C++

class Solution {
public:
    vector<int> findEvenNumbers(vector<int>& digits) {
        int num_times[10]={0,0,0,0,0,0,0,0,0,0};
        int num2_times[10];
        int digits_size;
        int i,digit1, digit2, digit3;
        int digit1_num, digit2_num, digit3_num;
        vector<int> ans;
        digits_size=digits.size();
        cout << "digits_size=" << digits_size << endl;
        for (int num:digits)
        {
            num_times[num]++;
        }
        
        for (i=100;i<1000;i+=2)
        {
            digit3=i%10;
            digit2=(i/10)%10;
            digit1=(i/100)%10;
            num2_times[digit3]=num_times[digit3];
            num2_times[digit2]=num_times[digit2];
            num2_times[digit1]=num_times[digit1];
            num2_times[digit3]=num2_times[digit3]-1;
            num2_times[digit2]=num2_times[digit2]-1;
            num2_times[digit1]=num2_times[digit1]-1;

            if ((num2_times[digit1]>=0)&&(num2_times[digit2]>=0)&&(num2_times[digit3]>=0))
                ans.push_back(i);
        }
        return ans;
    }
};