当前位置：首页 > news >正文

力扣热题——找出 3 位偶数

news 2025/5/16 8:08:02

题目链接：2094. 找出 3 位偶数 - 力扣（LeetCode）

题目描述

解法一：暴力枚举

Java写法：

C++写法：

C写法：

运行时间

时间复杂度和空间复杂度

解法二：计数数组来统计

思路解析

Java写法：

C++写法：

运行时间

时间复杂度和空间复杂度

总结

题目链接：2094. 找出 3 位偶数 - 力扣（LeetCode）

注：下述题目描述和示例均来自力扣

这题打开就发现做过了。

题目描述

给你一个整数数组 digits ，其中每个元素是一个数字（0 - 9）。数组中可能存在重复元素。

你需要找出所有满足下述条件且 互不相同 的整数：

该整数由 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]
解释：
同样的数字（0 - 9）在构造整数时可以重复多次，重复次数最多与其在 digits 中出现的次数一样。 
在这个例子中，数字 8 在构造 288、828 和 882 时都重复了两次。

示例 3：

输入：digits = [3,7,5]
输出：[]
解释：
使用给定的 digits 无法构造偶数。

解法一：暴力枚举

通过暴力枚举的方式来找出所有符合条件的三位数，并确保这些三位数满足题目给定的条件：没有前导零、是偶数且由 digits 数组中的三个不同元素组成。以下是具体步骤：

初始化集合：
- 使用一个 HashSet 来存储符合条件的数字，利用集合的特性（不允许重复元素）来自动去重。
三层循环遍历：
- 通过三层嵌套的 for 循环，分别选取三位数字的不同位置。外层循环变量 i 代表百位数字的位置，中层循环变量 j 代表十位数字的位置，内层循环变量 k 代表个位数字的位置。
- 在每一层循环中检查当前选择的三个位置是否相同，如果相同则跳过此次循环（避免选取相同的数字作为不同的位），这保证了我们每次组合都是基于三个不同的数字位置。
条件判断与数字构造：
- 对于每一个可能的组合，首先构造出对应的整数 num = digits[i] * 100 + digits[j] * 10 + digits[k]。
- 然后检查该整数是否大于等于100（确保是一个三位数），并且是个偶数（即 num % 2 == 0），这样就同时保证了没有前导零和是偶数的要求。
结果处理：
- 将所有符合条件的数字加入到集合中。
- 最后，将集合转换为数组，并对数组进行排序，以满足输出要求（按递增顺序排列）。

Java写法：

class Solution {public int[] findEvenNumbers(int[] digits) {int len = digits.length;// 这里使用集合的原因主要是java中数组的长度是事先固定的，但是我们又不知道长度，所以采用集合Set<Integer> set = new HashSet<>();// 三层for循环解决问题for (int i = 0; i < len; i++) {for (int j = 0; j < len; j++) {for (int k = 0; k < len; k++) {// 重复位置跳过if (i == j || j == k || i == k) {continue;}// 判断是否满足条件int num = digits[i] * 100 + digits[j] * 10 + digits[k];if (num >= 100 && num % 2 == 0) {// 满足条件加入集合set.add(num);}}}}// 集合转化为 int数组int[] res = set.stream().mapToInt(Integer::intValue).toArray();// 从小到大排序Arrays.sort(res);return res;}
}

C++写法：

class Solution {
public:vector<int> findEvenNumbers(vector<int>& digits) {int len = digits.size();std::set<int> s;for (int i = 0; i < len; i++) {for (int j = 0; j < len; j++) {for (int k = 0; k < len; k++) {// 重复位置跳过if (i == j || j == k || i == k) {continue;}// 判断是否满足条件int num = digits[i] * 100 + digits[j] * 10 + digits[k];if (num >= 100 && num % 2 == 0) {// 满足条件加入集合s.insert(num);}}}}// 集合转化为 vectorstd::vector<int> res(s.begin(), s.end());// 从小到大排序std::sort(res.begin(), res.end());return res;}
};

C写法：


// 定义比较函数用于排序
int compare(const void *a, const void *b) {return (*(int *)a - *(int *)b);
}// 判断是否为偶数
int isEven(int num) {return num % 2 == 0;
}int* findEvenNumbers(int* digits, int digitsSize, int* returnSize) {// 生成所有可能的三位数int count = 0;int maxResultSize = digitsSize * digitsSize * digitsSize;int* result = (int*)malloc(sizeof(int) * maxResultSize);int* isVisited = (int*)calloc(1000, sizeof(int));for (int i = 0; i < digitsSize; i++) {for (int j = 0; j < digitsSize; j++) {for (int k = 0; k < digitsSize; k++) {// 判断索引是否相同if (i != j && i != k && j != k) {// 将三个数字按顺序连接成三位数int number = digits[i] * 100 + digits[j] * 10 + digits[k];// 检查是否满足条件且未访问过if (isEven(number) && number >= 100 && number <= 999 && !isVisited[number]) {result[count++] = number;isVisited[number] = 1;}}}}}// 如果没有找到符合条件的数字，则返回空数组if (count == 0) {free(result);free(isVisited);*returnSize = 0;return NULL;}// 排序结果数组qsort(result, count, sizeof(int), compare);// 动态分配内存以保存结果int* finalResult = (int*)malloc(sizeof(int) * count);for (int i = 0; i < count; i++) {finalResult[i] = result[i];}// 释放内存free(result);free(isVisited);// 更新返回结果的大小*returnSize = count;return finalResult;
}

运行时间

时间复杂度和空间复杂度

解法二：计数数组来统计

思路解析

统计数字频率：
- 使用一个大小为10的数组（因为数字范围是0到9）来记录每个数字在输入数组中的出现次数。这一步允许我们快速检查某个数字是否可用以及它还剩余多少次使用机会。
构造符合条件的三位数：
- 枚举所有可能的三位数组合 (a, b, c)，其中：
  - a（百位）不能为0（否则会导致前导零），因此它的取值范围是1到9。
  - c（个位）必须是偶数，以保证生成的数字是偶数，所以它的取值只能是0, 2, 4, 6, 8。
  - 对于每一个(a, b, c)组合，首先确保对应的计数器值大于0（即该数字在原数组中有足够的数量供使用）。
  - 如果满足条件，则根据公式 num = a * 100 + b * 10 + c 计算出当前组合代表的实际数字，并将其添加到结果集中。
回溯与更新计数器：
- 每当选择了一个数字作为某一位（比如百位或十位或个位）时，相应地减少其计数器的值。一旦完成当前组合的所有可能性探索后，需要将计数器值恢复（回溯），以便下一次迭代可以正确计算。
排序并返回结果：
- 因为题目要求返回的结果需要按升序排列，所以在收集完所有符合条件的三位数之后，对这些数字进行排序。
- 在Java和C++中，分别使用了TreeSet和set自动去重并排序；而在C语言中，使用qsort函数对结果进行排序。

Java写法：

import java.util.*;public class Solution {public int[] findEvenNumbers(int[] digits) {// 计数数组，用于记录每个数字出现的次数int[] count = new int[10];for (int digit : digits) {count[digit]++;}// 使用TreeSet自动排序且去重Set<Integer> res = new TreeSet<>();// 遍历所有可能的百位、十位、个位数字for (int a = 1; a <= 9; a++) { // 百位不能为0if (count[a] == 0) continue;count[a]--; // 使用a后减少其计数for (int b = 0; b <= 9; b++) {if (count[b] == 0) continue;count[b]--;for (int c = 0; c <= 8; c += 2) { // 个位必须是偶数if (count[c] == 0) continue;int num = a * 100 + b * 10 + c;res.add(num);}count[b]++; // 回溯}count[a]++; // 回溯}// 转换为数组返回return res.stream().mapToInt(Integer::intValue).toArray();}
}

C++写法：

#include <vector>
#include <set>
using namespace std;class Solution {
public:vector<int> findEvenNumbers(vector<int>& digits) {// 计数数组，用于记录每个数字出现的次数vector<int> count(10, 0);for (int digit : digits) {count[digit]++;}// 使用set自动排序且去重set<int> res;// 遍历所有可能的百位、十位、个位数字for (int a = 1; a <= 9; ++a) { // 百位不能为0if (count[a] == 0) continue;count[a]--; // 使用a后减少其计数for (int b = 0; b <= 9; ++b) {if (count[b] == 0) continue;count[b]--;for (int c = 0; c <= 8; c += 2) { // 个位必须是偶数if (count[c] == 0) continue;int num = a * 100 + b * 10 + c;res.insert(num);}count[b]++; // 回溯}count[a]++; // 回溯}// 转换为vector返回return vector<int>(res.begin(), res.end());}
};

运行时间

时间复杂度和空间复杂度

总结

介绍了两种解决“找出由给定数字数组中的三个不同元素组成的三位偶数”问题的方法。第一种方法是暴力枚举，通过三层嵌套循环遍历所有可能的数字组合，确保没有前导零且为偶数，并使用集合去重和排序。第二种方法利用计数数组统计每个数字的频率，通过回溯法构造符合条件的三位数，并使用集合自动去重和排序。两种方法均能有效解决问题，但第二种方法在效率上更优，尤其是在处理较大数据集时。

查看全文

http://www.xdnf.cn/news/446455.html