Easy

题目描述

给你一个整数数组 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 <= digits.length <= 100
  • 0 <= digits[i] <= 9

解题思路

解题思路

这是一道典型的数字排列组合题目。我们需要从给定数字中选择三个数字组成三位偶数。

方法一：暴力枚举（推荐） 由于三位偶数的范围是 100-998，且必须是偶数，所以可能的答案只有 450 个。我们可以枚举所有可能的三位偶数（100, 102, 104, …, 998），然后检查每个数字是否能由给定的数字数组构成。

具体步骤：

  1. 统计输入数组中每个数字的出现次数
  2. 枚举所有三位偶数（从 100 到 998，步长为 2）
  3. 对每个三位偶数，检查其各位数字是否在原数组中有足够的数量
  4. 如果可以构成，则加入结果集

方法二：排列组合 使用三重循环枚举所有可能的三位数组合，检查是否满足条件。但这种方法相对复杂，需要处理重复数字的使用。

第一种方法更简洁高效，因为枚举空间有限且检查过程简单。

代码实现

class Solution {
public:
    vector<int> findEvenNumbers(vector<int>& digits) {
        vector<int> count(10, 0);
        for (int digit : digits) {
            count[digit]++;
        }
        
        vector<int> result;
        for (int num = 100; num <= 998; num += 2) {
            vector<int> needed(10, 0);
            int temp = num;
            needed[temp % 10]++;
            temp /= 10;
            needed[temp % 10]++;
            temp /= 10;
            needed[temp]++;
            
            bool canForm = true;
            for (int i = 0; i < 10; i++) {
                if (needed[i] > count[i]) {
                    canForm = false;
                    break;
                }
            }
            
            if (canForm) {
                result.push_back(num);
            }
        }
        
        return result;
    }
};

class Solution:
    def findEvenNumbers(self, digits: List[int]) -> List[int]:
        from collections import Counter
        
        count = Counter(digits)
        result = []
        
        for num in range(100, 999, 2):
            needed = Counter([num // 100, (num // 10) % 10, num % 10])
            
            can_form = True
            for digit, freq in needed.items():
                if count[digit] < freq:
                    can_form = False
                    break
            
            if can_form:
                result.append(num)
        
        return result

public class Solution {
    public int[] FindEvenNumbers(int[] digits) {
        int[] count = new int[10];
        foreach (int digit in digits) {
            count[digit]++;
        }
        
        List<int> result = new List<int>();
        for (int num = 100; num <= 998; num += 2) {
            int[] needed = new int[10];
            int temp = num;
            needed[temp % 10]++;
            temp /= 10;
            needed[temp % 10]++;
            temp /= 10;
            needed[temp]++;
            
            bool canForm = true;
            for (int i = 0; i < 10; i++) {
                if (needed[i] > count[i]) {
                    canForm = false;
                    break;
                }
            }
            
            if (canForm) {
                result.Add(num);
            }
        }
        
        return result.ToArray();
    }
}

var findEvenNumbers = function(digits) {
    const count = new Array(10).fill(0);
    for (const digit of digits) {
        count[digit]++;
    }
    
    const result = [];
    for (let num = 100; num <= 998; num += 2) {
        const needed = new Array(10).fill(0);
        let temp = num;
        needed[temp % 10]++;
        temp = Math.floor(temp / 10);
        needed[temp % 10]++;
        temp = Math.floor(temp / 10);
        needed[temp]++;
        
        let canForm = true;
        for (let i = 0; i < 10; i++) {
            if (needed[i] > count[i]) {
                canForm = false;
                break;
            }
        }
        
        if (canForm) {
            result.push(num);
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小
时间复杂度O(1)
空间复杂度O(1)

说明：

  • 时间复杂度：枚举所有三位偶数共450个，每次检查需要常数时间，总体为常数时间复杂度
  • 空间复杂度：只使用了固定大小的数组来统计数字出现次数，为常数空间复杂度

相关题目