华为OD机试真题——找出两个整数数组中同时出现的整数（2025A卷：100分）Ja ...

万万哇  论坛元老 | 2025-4-17 15:41:06 | 显示全部楼层 | 阅读模式
打印 上一主题 下一主题
楼主

主题 1679|帖子 1679|积分 5037


   2025 A卷 100分 题型
    本文涵盖详细的问题分析、解题思路、代码实现、代码详解、测试用例以及综合分析；
并提供Java、python、JavaScript、C++、C语言、GO六种语言的最佳实现方式！
  华为OD机试真题《找出两个整数数组中同时出现的整数》：

  
标题名称：找出两个整数数组中同时出现的整数

属性内容知识点哈希表、计数统计、排序时间限制1秒空间限制256MB限定语言不限
标题形貌

给定两个整数数组（数组元素范围在[-1000,1000]），找出所有在两个数组中同时出现的整数，并按升序排列返回。若同一数字在两个数组中出现的次数差异，则按较小次数输出（比方：数字3在数组A出现2次、数组B出现3次，则结果中输出两个3）。若不存在共同整数，返回空数组。
输入形貌
两行输入：
第一行为数组A的数字，用逗号分隔，比方：1,2
,3,1
第二行为数组B的数字，用逗号分隔，比方：1,1,2
,4
输出形貌
输出结果按升序排列，用逗号分隔。比方：1,1,2
（A和B中均包含1和2，其中1出现2次且取较小次数2，2出现1次）。若无交集，输出空字符串。
测试用例

  • 输入：
    1,2
    ,3
    1,1,2

    输出：1,2

  • 输入：
    5,5,5
    6
    输出： （空）
Java

问题分析

给定两个整数数组，找出所有在两个数组中同时出现的整数，并按升序排列返回。若同一数字在两个数组中出现次数差异，则按较小次数输出。若不存在共同整数，返回空数组。
解题思路


  • 读取输入：将输入的字符串转换为两个整数数组。
  • 统计次数：使用哈希表统计每个数字在两个数组中的出现次数。
  • 求交集：找出两个哈希表中都存在的数字，并取出现次数的较小值。
  • 生成结果：将每个数字按较小次数重复添加到结果列表。
  • 排序输出：对结果列表升序排列，并转换为逗号分隔的字符串。
代码实现

  1. import java.util.*;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         // 1. 读取输入
  6.         Scanner scanner = new Scanner(System.in);
  7.         String lineA = scanner.nextLine();
  8.         String lineB = scanner.nextLine();
  9.         scanner.close();
  11.         // 2. 分割字符串并转换为整数数组
  12.         String[] partsA = lineA.split(",");
  13.         int[] arrayA = new int[partsA.length];
  14.         for (int i = 0; i < partsA.length; i++) {
  15.             arrayA[i] = Integer.parseInt(partsA[i]);
  16.         }
  18.         String[] partsB = lineB.split(",");
  19.         int[] arrayB = new int[partsB.length];
  20.         for (int i = 0; i < partsB.length; i++) {
  21.             arrayB[i] = Integer.parseInt(partsB[i]);
  22.         }
  24.         // 3. 统计数组A中各数字的出现次数
  25.         Map<Integer, Integer> countA = new HashMap<>();
  26.         for (int num : arrayA) {
  27.             countA.put(num, countA.getOrDefault(num, 0) + 1);
  28.         }
  30.         // 4. 统计数组B中各数字的出现次数
  31.         Map<Integer, Integer> countB = new HashMap<>();
  32.         for (int num : arrayB) {
  33.             countB.put(num, countB.getOrDefault(num, 0) + 1);
  34.         }
  36.         // 5. 遍历交集并生成结果列表
  37.         List<Integer> result = new ArrayList<>();
  38.         for (int num : countA.keySet()) {
  39.             if (countB.containsKey(num)) {
  40.                 int minCount = Math.min(countA.get(num), countB.get(num));
  41.                 for (int i = 0; i < minCount; i++) {
  42.                     result.add(num);
  43.                 }
  44.             }
  45.         }
  47.         // 6. 对结果列表排序
  48.         Collections.sort(result);
  50.         // 7. 格式化输出
  51.         StringBuilder output = new StringBuilder();
  52.         for (int i = 0; i < result.size(); i++) {
  53.             output.append(result.get(i));
  54.             if (i < result.size() - 1) {
  55.                 output.append(",");
  56.             }
  57.         }
  58.         System.out.println(output);
  59.     }
  60. }
复制代码
代码详细解析


  • 读取输入：

    • 使用 Scanner 读取两行输入字符串。
    • split(",") 将字符串按逗号分割成字符串数组。
    • 转换为整数数组 arrayA 和 arrayB。

  • 统计次数：

    • HashMap 存储每个数字及其出现次数。
    • countA.getOrDefault(num, 0) + 1 实现计数。

  • 求交集：

    • 遍历 countA 的键集合，检查是否存在于 countB。
    • 若存在，取两次数的最小值，循环添加该数字到结果列表。

  • 排序与输出：

    • Collections.sort(result) 对结果升序排列。
    • StringBuilder 构建输出字符串，用逗号分隔元素。

测试示例

示例1：


  • 输入：
    1. 1,2
    2. ,3
    3. 1,1,2
    复制代码
  • 输出：1,2

  • 解析：1在A中出现1次，B中出现2次 → 取1次；2均出现1次 → 取1次。
示例2：


  • 输入：
    1. 5,5,5
    2. 6
    复制代码
  • 输出：空字符串
  • 解析：无共同数字。
综合分析


  • 时间复杂度：

    • 统计次数：O(n + m)，遍历两个数组。
    • 求交集：O(k)，k为共同数字数目。
    • 排序：O(r log r)，r为结果元素总数。
    • 总体时间复杂度为线性级别，适用于大数据量。

  • 空间复杂度：

    • 哈希表存储次数：O(n + m)。
    • 结果列表：O®。

  • 上风：

    • 哈希表高效统计：快速查找和统计次数。
    • 最小次数处置惩罚：直接比力并取较小值。
    • 逻辑清晰：分步骤处置惩罚，易于理解和维护。

  • 适用性：

    • 支持负数和大范围整数。
    • 处置惩罚大规模数据时性能稳定。

python

问题分析

我们须要找出两个整数数组中共同存在的所有整数，并按升序排列返回。如果同一个数字在两个数组中的出现次数差异，则按照较小的次数输出。比方，数组A中有3出现2次，数组B中有3出现3次，结果中须要输出两个3。如果没有共同数字，返回空数组。
输入输出示例：


  • 输入：两行逗号分隔的整数。
  • 输出：共同数字按升序排列的逗号分隔字符串，或空字符串。
解题思路


  • 输入处置惩罚：将输入的字符串转换为整数列表。
  • 统计次数：用哈希表统计每个数字在两个数组中的出现次数。
  • 求交集：找到两个数组中共同存在的数字，并取较小的出现次数。
  • 生成结果：按较小次数将数字重复添加到结果列表，并排序。
  • 输特殊式：将结果列表转换为逗号分隔的字符串。
代码实现

  1. from collections import Counter
  3. # 步骤1：读取输入并转换为整数列表
  4. a = list(map(int, input().split(',')))  # 输入示例："1,2
  5. ,3,1" → [1,2
  6. ,3,1]
  7. b = list(map(int, input().split(',')))  # 输入示例："1,1,2
  8. ,4" → [1,1,2
  9. ,4]
  11. # 步骤2：统计每个数字的出现次数
  12. count_a = Counter(a)  # 示例结果：Counter({1: 2, 2: 1, 3: 1})
  13. count_b = Counter(b)  # 示例结果：Counter({1: 2, 2: 1, 4: 1})
  15. # 步骤3：求交集，保留较小次数
  16. common = count_a & count_b  # 示例结果：Counter({1: 2, 2: 1})
  18. # 步骤4：生成结果列表并按升序排列
  19. result = sorted(common.elements())  # 示例结果：[1, 1, 2]
  21. # 步骤5：格式化输出
  22. print(','.join(map(str, result)) if result else '')  # 示例输出："1,1,2
  23. "
复制代码
代码解析


  • 读取输入

    • input().split(',')：将输入字符串按逗号分割成字符串列表。

      • 比方，输入 "1,2
        ,3,1" 会被转换为 ["1", "2", "3", "1"]。

    • map(int, ...)：将每个字符串转换为整数。

      • map(int, ["1", "2", "3", "1"]) → [1, 2, 3, 1]。


  • 统计次数

    • Counter(a)：统计列表 a 中每个数字的出现次数，返回一个类似字典的对象。

      • 比方，a = [1,2
        ,3,1] → Counter({1:2, 2:1, 3:1})。

    • Counter(b)：同理统计数组 b 的次数。

  • 求交集

    • count_a & count_b：这是 Counter 的交集操作，返回一个新的 Counter。

      • 键：两个 Counter 中都存在的数字（即共同数字）。
      • 值：两个 Counter 中对应键的较小值。
      • 比方，count_a = {1:2, 2:1}，count_b = {1:3, 2:1} → common = {1:2, 2:1}。


  • 生成结果

    • common.elements()：返回一个迭代器，每个元素按其次数重复。

      • common = {1:2, 2:1} → 迭代器生成 [1, 1, 2]。

    • sorted()：对结果列表进行升序排序。

      • 比方，[1, 1, 2] 已经是升序，无需调解。


  • 格式化输出

    • ','.join(map(str, result))：将整数列表转换为逗号分隔的字符串。

      • [1, 1, 2] → "1,1,2
        "。

    • if result else ''：处置惩罚空结果的情况，直接输出空字符串。

测试示例

示例1：
  1. 输入：
  2. 1,2
  3. ,3,1
  4. 1,1,2
  5. ,4
  7. 输出：
  8. 1,1,2
复制代码
解析：


  • 数组A中1出现2次，数组B中1出现2次 → 取2次。
  • 数组A中2出现1次，数组B中2出现1次 → 取1次。
  • 结果列表 [1,1,2
    ]，排序后输出 1,1,2
    。
示例2：
  1. 输入：5,5,5
  2. 6
  3. 输出：（空字符串）
复制代码
解析：


  • 数组A中5出现3次，数组B中没有5 → 无共同数字。
  • 结果列表为空，输出空字符串。
综合分析


  • 时间复杂度

    • 统计次数：O(n + m)，其中 n 和 m 是两个数组的长度。
    • 求交集：O(k)，k 是两个数组中共同数字的数目。
    • 排序：O(r log r)，其中 r 是结果元素的总数。
    • 总复杂度：O(n + m + r log r)，得当处置惩罚大规模数据。

  • 空间复杂度

    • 哈希表：O(n + m) 存储两个数组的统计结果。
    • 结果列表：O® 存储终极输出的元素。

  • 上风

    • 高效统计：Counter 是Python标准库的高效工具，自动统计次数。
    • 代码简便：集合操作（&）和元素展开（elements()）简化了复杂逻辑。
    • 通用性：支持负数、零和正数，覆盖标题要求的全部范围。

  • 适用场景

    • 须要快速找出两个数组的公共元素。
    • 处置惩罚元素重复次数统计的场景。
    • 适用于数据量较大的整数数组（比方元素数在10^6级别）。

JavaScript

问题分析

我们须要找出两个整数数组中共同存在的所有整数，并按升序排列返回。如果同一数字在两个数组中出现次数差异，则按较小次数输出。比方，数组A中数字3出现2次，数组B中出现3次，结果中输出两个3。若没有共同数字，返回空数组。
解题思路


  • 读取输入：将输入的两行字符串转换为整数数组。
  • 统计次数：用对象统计每个数字在两个数组中的出现次数。
  • 求交集：找到两个数组中共同存在的数字，并取较小次数。
  • 生成结果：将每个数字按较小次数重复添加到结果数组。
  • 排序输出：将结果数组排序后转换为逗号分隔的字符串。
代码实现

  1. const readline = require('readline');
  3. const rl = readline.createInterface({
  4.   input: process.stdin,
  5.   output: process.stdout
  6. });
  8. let input = [];
  9. rl.on('line', (line) => {
  10.   input.push(line.trim()); // 读取输入并去除两端空格
  11.   if (input.length === 2) {
  12.     main();   // 当读取到两行输入后执行主逻辑
  13.     rl.close();
  14.   }
  15. });
  17. function main() {
  18.   // 1. 将输入转换为整数数组
  19.   const a = input[0].split(',').map(Number);
  20. // 示例输入 "1,2
  21. ,3" → [1,2
  22. ,3]
  23.   const b = input[1].split(',').map(Number); // 示例输入 "1,1,2
  24. " → [1,1,2
  25. ]
  27.   // 2. 统计每个数字的出现次数
  28.   const countA = {};
  29.   a.forEach(num => {
  30.     countA[num] = (countA[num] || 0) + 1; // 若数字不存在则初始化为0，再加1
  31.   });
  33.   const countB = {};
  34.   b.forEach(num => {
  35.     countB[num] = (countB[num] || 0) + 1;
  36.   });
  38.   // 3. 遍历所有数字，找出公共数字并取较小次数
  39.   const result = [];
  40.   Object.keys(countA).forEach(numStr => { // 遍历数组A的所有数字（字符串键）
  41.     const num = parseInt(numStr, 10);     // 将字符串键转换为数字
  42.     if (countB.hasOwnProperty(numStr)) {   // 检查是否在数组B中存在
  43.       const min = Math.min(countA[numStr], countB[numStr]); // 取较小次数
  44.       for (let i = 0; i < min; i++) {     // 按次数重复添加数字
  45.         result.push(num);
  46.       }
  47.     }
  48.   });
  50.   // 4. 排序并输出结果
  51.   result.sort((a, b) => a - b);           // 升序排序
  52.   console.log(result.length > 0 ? result.join(',') : ''); // 转换为逗号字符串
  53. }
复制代码
代码解析


  • 读取输入
    1. const a = input[0].split(',').map(Number);
    复制代码

    • split(',')：将字符串按逗号分割成字符串数组（比方 "1,2
      ,3" → ["1", "2", "3"]）。
    • map(Number)：将每个字符串转换为数字（比方 "1" → 1）。

  • 统计次数
    1. const countA = {};
    2. a.forEach(num => {
    3.   countA[num] = (countA[num] || 0) + 1;
    4. });
    复制代码

    • 使用对象 countA 统计数组 a 中每个数字的出现次数。
    • countA[num] || 0：如果数字不存在则初始化为0。
    • 示例：数组 [1, 2, 3, 1] → countA = {1: 2, 2: 1, 3: 1}。

  • 求交集
    1. Object.keys(countA).forEach(numStr => {
    2.   const num = parseInt(numStr, 10);
    3.   if (countB.hasOwnProperty(numStr)) {
    4.     const min = Math.min(countA[numStr], countB[numStr]);
    5.     for (let i = 0; i < min; i++) {
    6.       result.push(num);
    7.     }
    8.   }
    9. });
    复制代码

    • Object.keys(countA)：获取数组A中所有数字的字符串键（比方 ["1", "2", "3"]）。
    • parseInt(numStr, 10)：将字符串键转换为数字（比方 "1" → 1）。
    • countB.hasOwnProperty(numStr)：检查数组B中是否存在该数字。
    • Math.min()：取两个数组中较小的次数。

  • 生成结果
    1. result.sort((a, b) => a - b);
    复制代码

    • sort((a, b) => a - b)：对结果数组升序排序（比方 [2, 1] → [1, 2]）。

  • 输出结果
    1. console.log(result.length > 0 ? result.join(',') : '');
    复制代码

    • result.join(',')：将数组转换为逗号分隔的字符串（比方 [1, 2] → "1,2
      "）。

测试示例

示例1：
  1. 输入：1,2
  2. ,3
  3. 1,1,2
  5. 输出：1,2
复制代码
解析：


  • 数组A：1出现1次，2出现1次，3出现1次。
  • 数组B：1出现2次，2出现1次，4出现1次。
  • 公共数字1（取1次）和2（取1次），排序后输出 1,2
    。
示例2：
  1. 输入：5,5,5
  2. 6
  3. 输出：（空字符串）
复制代码
解析：


  • 数组A：5出现3次，数组B：6出现1次。
  • 无共同数字，输出空字符串。
综合分析


  • 时间复杂度

    • 统计次数：O(n + m)，遍历两个数组各一次。
    • 求交集：O(k)，k为数组A中差异数字的数目。
    • 排序：O(r log r)，r为结果元素总数。
    • 总复杂度：O(n + m + r log r)，得当处置惩罚大规模数据。

  • 空间复杂度

    • 统计对象：O(n + m)，存储两个数组的统计结果。
    • 结果数组：O®，存储终极输出的元素。

  • 上风

    • 高效统计：对象快速统计数字出现次数。
    • 逻辑清晰：分步骤处置惩罚，易于理解和维护。
    • 通用性：支持负数和大范围整数（标题范围[-1000, 1000]）。

  • 适用场景

    • 须要快速统计和处置惩罚重复元素的场景。
    • 数据规模较大时仍能保持高效性能。

C++

问题分析

给定两个整数数组，找出所有在两个数组中同时出现的整数，并按升序排列返回。若同一数字在两个数组中出现次数差异，则按较小次数输出。若不存在共同整数，返回空数组。
解题思路


  • 输入处置惩罚：将输入的字符串分割为整数数组。
  • 统计次数：使用哈希表统计每个数字在两个数组中的出现次数。
  • 求交集：找到两个哈希表中共同存在的数字，并取较小次数。
  • 生成结果：将每个共同数字按较小次数重复添加到结果数组。
  • 排序输出：对结果数组排序并格式化为逗号分隔的字符串。
代码实现

  1. #include <iostream>
  2. #include <vector>
  3. #include <unordered_map>
  4. #include <sstream>
  5. #include <algorithm>
  7. using namespace std;
  9. // 将字符串分割为整数数组
  10. vector<int> split(const string &s) {
  11.     vector<int> res;
  12.     stringstream ss(s);
  13.     string item;
  14.     while (getline(ss, item, ',')) {
  15.         res.push_back(stoi(item));
  16.     }
  17.     return res;
  18. }
  20. int main() {
  21.     string lineA, lineB;
  22.    
  23.     // 1. 读取输入
  24.     getline(cin, lineA);
  25.     getline(cin, lineB);
  26.    
  27.     // 2. 分割字符串为整数数组
  28.     vector<int> A = split(lineA);
  29.     vector<int> B = split(lineB);
  30.    
  31.     // 3. 统计每个数字的出现次数
  32.     unordered_map<int, int> countA, countB;
  33.     for (int num : A) countA[num]++;
  34.     for (int num : B) countB[num]++;
  35.    
  36.     // 4. 遍历哈希表，生成结果数组
  37.     vector<int> result;
  38.     for (auto &pair : countA) {
  39.         int num = pair.first;
  40.         if (countB.find(num) != countB.end()) {
  41.             int min_count = min(pair.second, countB[num]);
  42.             for (int i = 0; i < min_count; ++i) {
  43.                 result.push_back(num);
  44.             }
  45.         }
  46.     }
  47.    
  48.     // 5. 排序并输出结果
  49.     sort(result.begin(), result.end());
  50.     ostringstream oss;
  51.     for (size_t i = 0; i < result.size(); ++i) {
  52.         if (i != 0) oss << ",";
  53.         oss << result[i];
  54.     }
  55.     cout << (result.empty() ? "" : oss.str()) << endl;
  56.    
  57.     return 0;
  58. }
复制代码
代码详细解析


  • 输入处置惩罚：
    1. getline(cin, lineA);  // 读取第一行输入
    2. getline(cin, lineB);  // 读取第二行输入
    复制代码

    • getline 读取整行输入，确保正确处置惩罚带空格的字符串。

  • 字符串分割：
    1. vector<int> split(const string &s) {
    2.     vector<int> res;
    3.     stringstream ss(s);
    4.     string item;
    5.     while (getline(ss, item, ',')) {
    6.         res.push_back(stoi(item));
    7.     }
    8.     return res;
    9. }
    复制代码

    • stringstream 分割字符串，按逗号分隔并转换为整数存入数组。

  • 统计次数：
    1. unordered_map<int, int> countA, countB;
    2. for (int num : A) countA[num]++;
    3. for (int num : B) countB[num]++;
    复制代码

    • 使用 unordered_map 统计每个数字出现的次数，时间复杂度为 O(n)。

  • 生成结果数组：
    1. for (auto &pair : countA) {
    2.     int num = pair.first;
    3.     if (countB.find(num) != countB.end()) {
    4.         int min_count = min(pair.second, countB[num]);
    5.         for (int i = 0; i < min_count; ++i) {
    6.             result.push_back(num);
    7.         }
    8.     }
    9. }
    复制代码

    • 遍历哈希表 countA 的键，检查是否存在于 countB 中。
    • 若存在，取较小次数，并将该数字重复添加到结果数组。

  • 排序输出：
    1. sort(result.begin(), result.end());
    2. ostringstream oss;
    3. for (size_t i = 0; i < result.size(); ++i) {
    4.     if (i != 0) oss << ",";
    5.     oss << result[i];
    6. }
    7. cout << (result.empty() ? "" : oss.str()) << endl;
    复制代码

    • sort 对结果数组升序排列。
    • ostringstream 将数组转换为逗号分隔的字符串。

测试示例

示例1：


  • 输入：
    1. 1,2
    2. ,3
    3. 1,1,2
    复制代码
  • 输出：1,2

  • 解析：共同数字1（取1次）、2（取1次），排序后输出 1,2
    。
示例2：


  • 输入：
    1. 5,5,5
    2. 6
    复制代码
  • 输出：空字符串
  • 解析：无共同数字，输出空。
综合分析


  • 时间复杂度：

    • 统计次数：O(n + m)，遍历两个数组各一次。
    • 求交集：O(k)，k为数组A中差异数字的数目。
    • 排序：O(r log r)，r为结果元素总数。
    • 总复杂度：O(n + m + r log r)，高效处置惩罚大规模数据。

  • 空间复杂度：

    • 哈希表：O(n + m)，存储两个数组的统计结果。
    • 结果数组：O®，存储终极输出的元素。

  • 上风：

    • 哈希表高效统计：快速查找和统计次数。
    • 最小次数处置惩罚：直接比力并取较小值。
    • 通用性：支持负数和大范围整数（标题范围[-1000, 1000]）。

  • 适用场景：

    • 须要快速处置惩罚重复元素的场景。
    • 数据规模较大时仍能保持高效性能。

C语言

问题分析

给定两个整数数组，找出所有在两个数组中同时出现的整数，并按升序排列返回。若同一数字在两个数组中出现次数差异，则按较小次数输出。若不存在共同整数，返回空数组。
解题思路


  • 输入处置惩罚：将输入的两行字符串分割为整数数组。
  • 统计次数：使用数组统计每个数字在两个数组中的出现次数（数字范围在[-1000, 1000]，直接用数组索引映射）。
  • 求交集：遍历所有可能的数字，找到两个数组中都存在的数字，并取较小次数。
  • 生成结果：按较小次数将数字重复添加到结果数组。
  • 排序输出：对结果数组排序后转换为逗号分隔的字符串。
代码实现

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  5. #define MIN_NUM -1000
  6. #define MAX_NUM 1000
  7. #define RANGE_SIZE (MAX_NUM - MIN_NUM + 1)  // 2001
  9. int compare_ints(const void *a, const void *b) {
  10.     return (*(int*)a - *(int*)b);  // 升序排序
  11. }
  13. void parse_input(const char *input, int **arr, int *size) {
  14.     char *buffer = strdup(input);  // 复制输入字符串
  15.     *size = 0;
  16.     int capacity = 10;
  17.     *arr = malloc(capacity * sizeof(int));
  19.     char *token = strtok(buffer, ",");  // 分割逗号
  20.     while (token != NULL) {
  21.         if (*size >= capacity) {  // 动态扩容
  22.             capacity *= 2;
  23.             *arr = realloc(*arr, capacity * sizeof(int));
  24.         }
  25.         (*arr)[(*size)++] = atoi(token);  // 转换为整数
  26.         token = strtok(NULL, ",");
  27.     }
  28.     free(buffer);  // 释放临时内存
  29. }
  31. int main() {
  32.     char lineA[10000], lineB[10000];
  33.     fgets(lineA, sizeof(lineA), stdin);  // 读取输入行A
  34.     fgets(lineB, sizeof(lineB), stdin);  // 读取输入行B
  36.     // 去除换行符
  37.     lineA[strcspn(lineA, "\n")] = '\0';
  38.     lineB[strcspn(lineB, "\n")] = '\0';
  40.     int *A, *B, sizeA, sizeB;
  41.     parse_input(lineA, &A, &sizeA);  // 解析数组A
  42.     parse_input(lineB, &B, &sizeB);  // 解析数组B
  44.     // 初始化计数数组为0
  45.     int countA[RANGE_SIZE] = {0};
  46.     int countB[RANGE_SIZE] = {0};
  48.     // 统计数组A中各数字的出现次数
  49.     for (int i = 0; i < sizeA; i++) {
  50.         int num = A[i];
  51.         if (num < MIN_NUM || num > MAX_NUM) continue;  // 过滤非法数字
  52.         countA[num - MIN_NUM]++;  // 转换为索引（-1000 → 0，1000 → 2000）
  53.     }
  55.     // 统计数组B中各数字的出现次数
  56.     for (int i = 0; i < sizeB; i++) {
  57.         int num = B[i];
  58.         if (num < MIN_NUM || num > MAX_NUM) continue;
  59.         countB[num - MIN_NUM]++;
  60.     }
  62.     // 计算总共有多少个元素需要输出
  63.     int total = 0;
  64.     for (int num = MIN_NUM; num <= MAX_NUM; num++) {
  65.         int idx = num - MIN_NUM;
  66.         if (countA[idx] > 0 && countB[idx] > 0) {
  67.             total += (countA[idx] < countB[idx]) ? countA[idx] : countB[idx];
  68.         }
  69.     }
  71.     // 生成结果数组
  72.     int *result = malloc(total * sizeof(int));
  73.     int pos = 0;
  74.     for (int num = MIN_NUM; num <= MAX_NUM; num++) {
  75.         int idx = num - MIN_NUM;
  76.         if (countA[idx] > 0 && countB[idx] > 0) {
  77.             int min_count = (countA[idx] < countB[idx]) ? countA[idx] : countB[idx];
  78.             for (int i = 0; i < min_count; i++) {
  79.                 result[pos++] = num;  // 按次数填充数字
  80.             }
  81.         }
  82.     }
  84.     // 对结果数组升序排序
  85.     qsort(result, total, sizeof(int), compare_ints);
  87.     // 生成输出字符串
  88.     if (total == 0) {
  89.         printf("");  // 无交集输出空字符串
  90.     } else {
  91.         char *output = malloc(total * 12);  // 预分配足够空间
  92.         int offset = 0;
  93.         for (int i = 0; i < total; i++) {
  94.             if (i > 0) offset += sprintf(output + offset, ",");  // 添加逗号分隔
  95.             offset += sprintf(output + offset, "%d", result[i]);
  96.         }
  97.         printf("%s", output);  // 输出结果
  98.         free(output);
  99.     }
  101.     // 释放动态内存
  102.     free(A);
  103.     free(B);
  104.     free(result);
  106.     return 0;
  107. }
复制代码
代码解析


  • 输入处置惩罚：

    • fgets 读取输入行，并去除换行符。
    • parse_input 函数分割逗号字符串为整数数组，支持动态扩容。

  • 统计次数：

    • 使用两个长度为2001的数组 countA 和 countB。
    • 数组索引通过 num - MIN_NUM 计算，将数字映射到[0, 2000]。

  • 求交集：

    • 遍历所有可能的数字（-1000到1000）。
    • 若数字在两个数组中都出现，取较小次数并累加到 total。

  • 生成结果：

    • 动态分配 result 数组，按较小次数添补数字。

  • 排序输出：

    • 使用 qsort 对结果数组升序排序。
    • 生成逗号分隔的字符串，无交集时输出空字符串。

测试示例

示例1输入：
  1. 1,2
  2. ,3
  3. 1,1,2
复制代码
输出：
  1. 1,2
复制代码
解析：


  • 数组A：1出现1次，2出现1次。
  • 数组B：1出现2次，2出现1次。
  • 交集取1次1和1次2，输出 1,2
    。
示例2输入：
  1. 5,5,5
  2. 6
复制代码
输出：
  1. （空字符串）
复制代码
解析：


  • 数组A中5出现3次，数组B中无5，输出空。
综合分析


  • 时间复杂度：

    • 统计次数：O(n + m)，遍历两个数组各一次。
    • 求交集：O(2001)，固定范围遍历。
    • 排序：O(total log total)，结果数组排序。
    • 总体复杂度为线性级别，得当处置惩罚大数据。

  • 空间复杂度：

    • 计数数组：O(2001)，固定大小。
    • 结果数组：O(total)，动态分配。

  • 上风：

    • 高效统计：数组索引直接映射数字，无需哈希冲突。
    • 代码简便：固定范围遍历制止复杂逻辑。
    • 内存安全：动态分配内存制止栈溢出。

  • 适用场景：

    • 数字范围已知且有限（如[-1000, 1000]）。
    • 须要高效处置惩罚重复元素的场景。

GO

问题分析

给定两个整数数组，找出所有在两个数组中同时出现的整数，并按升序排列返回。若同一数字在两个数组中出现次数差异，则按较小次数输出。若不存在共同整数，返回空数组。
解题思路


  • 读取输入：将输入的两行字符串解析为整数切片。
  • 统计次数：使用哈希表（map[int]int）统计每个数字的出现次数。
  • 求交集：遍历哈希表，找到共同数字并取较小次数。
  • 生成结果：将共同数字按较小次数重复添加到结果切片。
  • 排序输出：对结果切片升序排列并转换为逗号分隔的字符串。
代码实现

  1. package main
  3. import (
  4.         "bufio"
  5.         "fmt"
  6.         "os"
  7.         "sort"
  8.         "strconv"
  9.         "strings"
  10. )
  12. func main() {
  13.         // 读取输入
  14.         scanner := bufio.NewScanner(os.Stdin)
  15.         scanner.Scan()
  16.         lineA := scanner.Text() // 读取第一行输入
  17.         scanner.Scan()
  18.         lineB := scanner.Text() // 读取第二行输入
  20.         // 解析输入为整数切片
  21.         a := parseLine(lineA)
  22.         b := parseLine(lineB)
  24.         // 统计数字出现次数
  25.         countA := countNumbers(a)
  26.         countB := countNumbers(b)
  28.         // 生成结果切片
  29.         result := make([]int, 0)
  30.         for num, cntA := range countA {
  31.                 if cntB, exists := countB[num]; exists {
  32.                         minCount := cntA
  33.                         if cntB < minCount {
  34.                                 minCount = cntB
  35.                         }
  36.                         // 将数字按最小次数重复添加到结果
  37.                         for i := 0; i < minCount; i++ {
  38.                                 result = append(result, num)
  39.                         }
  40.                 }
  41.         }
  43.         // 排序结果
  44.         sort.Ints(result)
  46.         // 格式化输出
  47.         if len(result) == 0 {
  48.                 fmt.Println("")
  49.         } else {
  50.                 fmt.Println(strings.Join(strings.Fields(fmt.Sprint(result)), ","))
  51.         }
  52. }
  54. // 将字符串解析为整数切片
  55. func parseLine(line string) []int {
  56.         parts := strings.Split(line, ",")
  57.         nums := make([]int, len(parts))
  58.         for i, part := range parts {
  59.                 num, _ := strconv.Atoi(part) // 忽略错误，假设输入合法
  60.                 nums[i] = num
  61.         }
  62.         return nums
  63. }
  65. // 统计切片中数字的出现次数
  66. func countNumbers(nums []int) map[int]int {
  67.         count := make(map[int]int)
  68.         for _, num := range nums {
  69.                 count[num]++
  70.         }
  71.         return count
  72. }
复制代码
代码解析


  • 读取输入
    1. scanner := bufio.NewScanner(os.Stdin)
    2. scanner.Scan()
    3. lineA := scanner.Text()
    复制代码

    • 使用 bufio.Scanner 读取标准输入的两行字符串。

  • 解析输入
    1. func parseLine(line string) []int {
    2.     parts := strings.Split(line, ",")
    3.     nums := make([]int, len(parts))
    4.     for i, part := range parts {
    5.         num, _ := strconv.Atoi(part)
    6.         nums[i] = num
    7.     }
    8.     return nums
    9. }
    复制代码

    • strings.Split 按逗号分割字符串为子串。
    • strconv.Atoi 将子串转换为整数。

  • 统计次数
    1. func countNumbers(nums []int) map[int]int {
    2.     count := make(map[int]int)
    3.     for _, num := range nums {
    4.         count[num]++
    5.     }
    6.     return count
    7. }
    复制代码

    • 遍历整数切片，用 map[int]int 统计每个数字的出现次数。

  • 求交集并生成结果
    1. for num, cntA := range countA {
    2.     if cntB, exists := countB[num]; exists {
    3.         minCount := cntA
    4.         if cntB < minCount {
    5.             minCount = cntB
    6.         }
    7.         for i := 0; i < minCount; i++ {
    8.             result = append(result, num)
    9.         }
    10.     }
    11. }
    复制代码

    • 遍历 countA 的所有键，检查是否存在于 countB 中。
    • 若存在，取较小次数，并将数字按次数重复添加到结果切片。

  • 排序与输出
    1. sort.Ints(result)
    2. fmt.Println(strings.Join(strings.Fields(fmt.Sprint(result)), ","))
    复制代码

    • sort.Ints 对结果切片升序排列。
    • fmt.Sprint(result) 将切片转换为字符串，再更换空格为逗号。

测试示例

示例1：
  1. 输入：
  2. 1,2
  3. ,3,1
  4. 1,1,2
  5. ,4
  7. 输出：
  8. 1,1,2
复制代码
解析：


  • 数组A中1出现2次，数组B中1出现2次 → 取2次。
  • 数组A中2出现1次，数组B中2出现1次 → 取1次。
示例2：
  1. 输入：5,5,5
  2. 6
  3. 输出：（空字符串）
复制代码
解析：


  • 数组A中5出现3次，数组B中没有5 → 无共同数字。
综合分析


  • 时间复杂度

    • 统计次数：O(n + m)，遍历两个数组各一次。
    • 求交集：O(k)，k为数组A中差异数字的数目。
    • 排序：O(r log r)，r为结果元素总数。
    • 总复杂度：O(n + m + r log r)，得当处置惩罚大规模数据。

  • 空间复杂度

    • 哈希表：O(n + m)，存储两个数组的统计结果。
    • 结果切片：O®，存储终极输出的元素。

  • 上风

    • 高效统计：哈希表快速统计数字出现次数。
    • 简便逻辑：直接遍历哈希表，代码清晰易读。
    • 通用性：支持负数和大范围整数（标题范围[-1000, 1000]）。

  • 适用场景

    • 须要快速处置惩罚重复元素的场景。
    • 数据规模较大时仍能保持高效性能。

更多内容：

https://www.kdocs.cn/l/cvk0eoGYucWA
本文发表于【纪元A梦】，关注我，获取更多实用教程/资源！

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

本帖子中包含更多资源

您需要 登录 才可以下载或查看，没有账号？立即注册

x
回复

使用道具 举报

0 个回复

倒序浏览
返回列表

快速回复

高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 or 立即注册

本版积分规则

万万哇

论坛元老
这个人很懒什么都没写!

楼主热帖

标签云

AI 运维 CIO 存储 服务器
微信订阅号
微信服务号
微信客服
小程序
H5
关于我们 商务合作 网站地图
©Copyright 2022-2024 杭州祥升科技有限公司 版权所有 浙ICP备20004199号
快速回复 返回顶部 返回列表