题目描述与示例

题目描述

现有两个整数数组，需要你找出两个数组中同时出现的整数，并按照如下要求输出：

1、有同时出现的整数时，先按照同时出现次数（整数在两个数组中都出现并且出现次数较少的那个）进行归类，然后按照出现次数从小到大依次按行输出。

2、没有同时出现的整数时，输出NULL。

题目练习网址：https://www.algomooc.com/problem/P2853

输入描述

第一行为第一个整数数组，第二行为第二个整数数组，每行数据中整数与整数之间以英文逗号分隔，整数的取值范围为[-200,200]，数组长度的范围为[1,10000]之间的整数。

输出描述

按照出现次数从小到大依次按行输出，每行输出的格式为：出现次数:该出现次数下的整数``升序排序``的结果。

格式中的":"为英文冒号，整数间以英文逗号分隔。

示例一

输入

5,3,6,-8,0,11
2,8,8,8,-1,15

输出

NULL

说明

两个整数数组没有同时出现的整数，输出NULL。

示例二

输入

5,8,11,3,6,8,8,-1,11,2,11,11
11,2,11,8,6,8,8,-1,8,15,3,-9,11

输出

1:-1,2,3,6
3:8,11

说明

两个整数数组中同时出现的整数为-1、2、3、6、8、11，其中同时出现次数为1的整数为-1, 2, 3, 6(升序排序)，同时出现次数为3的整数为8,11(升序排序)，先升序输出出现次数为1的整数，再升序输出出现次数为3的整数。

解题思路

本题是一道非常典型的结合哈希表进行排序的问题，同学们其实已经接触了很多了。

数据预处理

首先我们需要统计在两个数组中，所有元素各自出现的个数。很容易想到使用Counter计数器来完成。

from collections import Counter, defaultdict

# 输入数据
lst1 = list(map(int, input().split(",")))
lst2 = list(map(int, input().split(",")))

# 用两个哈希表计数器，cnt1和cnt2来分别储存两个数组中元素出现的频次
cnt1 = Counter(lst1)
cnt2 = Counter(lst2)

由于我们要统计两个哈希表中的交集部分，且记录其中出现频次较小的值，我们可以构建一个新的哈希表cnt来储存数据。

可以通过推导式遍历cnt1中的键k，考虑k是否位于cnt2中来构建，而值为两个出现频次（不能为0）的较小值min(cnt1[k], cnt2[k])。即

# 构建哈希表cnt，用于储存同时出现在lst1和lst2中的元素，k为元素本身，v为两者之间的较小频次
cnt = {k: min(cnt1[k], cnt2[k]) for k in cnt1 if k in cnt2}

观察最后的输出格式，发现在cnt中出现次数相等的元素，将会在同一行被输出。

因此我们再构建一个哈希表dic，以出现次数为键key，而所有出现次数为key的元素构成的列表作为值value，来重新储存数据。即

# 再次构建一个哈希表dic，其默认值为list
# 在哈希表cnt中出现次数为键key，而所有出现次数为key的元素构成的列表作为值
dic = defaultdict(list)

# 遍历cnt中的所有键值对k, v
for k, v in cnt.items():
    # 将所有出现次数为v的元素k，储存在dic[v]这个列表中
    dic[v].append(k)

排序并输出结果

在构建得到dic之后，剩下的工作就非常简单了，只需要做简单的排序即可，而且并不需要使用到lambda匿名函数来完成复杂排序。

但是要注意此处是做了双重的排序。

由于最终的输出结果要先按照出现次数从小到大排序，因此我们可以对sorted(dic.keys())进行遍历，考虑其中出现的所有k。

对于每一个dic[k]，其对应的值列表也要再次进行从小到大的排序，即dic[k].sort()。

每一行具体的输出，则可以结合字符串格式化、字符串的join()方法和内置函数map()完成。

# 对dic中的键进行排序，并且进行遍历
for k in sorted(dic.keys()):
    # 对每一个键对应的值列表，都进行排序
    dic[k].sort()
    # 结合字符串格式化、字符串的join()方法和内置函数map()完成题目要求的输出
    s = ",".join(map(str, dic[k]))
    print(f"{k}:{s}")

当然，此处也要注意dic为空的情况，即lst1和lst2两个数组不存在任何元素重叠。

此时要输出字符串NULL。

故总体的代码为

# 如果dic为空，则输出NULL
if len(dic) == 0:
    print("NULL")
# 否则，对dic中的键进行排序，并且进行遍历
else:
    for k in sorted(dic.keys()):
        # 对每一个键对应的值列表，都进行排序
        dic[k].sort()
        # 结合字符串格式化、字符串的join()方法和内置函数map()完成题目要求的输出
        s = ",".join(map(str, dic[k]))
        print(f"{k}:{s}")

这样就完成了全部的代码。

代码

Python

# 欢迎来到「欧弟算法 - 华为OD全攻略」,收录华为OD题库、面试指南、八股文与学员案例！
# 地址：https://www.odalgo.com
# 华为OD机试刷题网站：https://www.algomooc.com
# 添加微信 278166530 获取华为 OD 笔试真题题库和视频

from collections import Counter, defaultdict

# 输入数据
lst1 = list(map(int, input().split(",")))
lst2 = list(map(int, input().split(",")))

# 用两个哈希表计数器，cnt1和cnt2来分别储存两个数组中元素出现的频次
cnt1 = Counter(lst1)
cnt2 = Counter(lst2)

# 构建哈希表cnt，用于储存同时出现在lst1和lst2中的元素，k为元素本身，v为两者之间的较小频次
cnt = {k: min(cnt1[k], cnt2[k]) for k in cnt1 if k in cnt2}

# 再次构建一个哈希表dic，其默认值为list
# 在哈希表cnt中出现次数为键key，而所有出现次数为key的元素构成的列表作为值
dic = defaultdict(list)

# 遍历cnt中的所有键值对k, v
for k, v in cnt.items():
    # 将所有出现次数为v的元素k，储存在dic[v]这个列表中
    dic[v].append(k)


# 如果dic为空，则输出NULL
if len(dic) == 0:
    print("NULL")
# 否则，对dic中的键进行排序，并且进行遍历
else:
    for k in sorted(dic.keys()):
        # 对每一个键对应的值列表，都进行排序
        dic[k].sort()
        # 结合字符串格式化、字符串的join()方法和内置函数map()完成题目要求的输出
        s = ",".join(map(str, dic[k]))
        print(f"{k}:{s}")

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取两行输入并按逗号分割为整数列表
        String[] tokens1 = scanner.nextLine().split(",");
        String[] tokens2 = scanner.nextLine().split(",");

        List<Integer> lst1 = new ArrayList<>();
        List<Integer> lst2 = new ArrayList<>();
        for (String token : tokens1) lst1.add(Integer.parseInt(token));
        for (String token : tokens2) lst2.add(Integer.parseInt(token));

        // cnt1 和 cnt2 用于记录两个数组中元素出现的次数
        Map<Integer, Integer> cnt1 = new HashMap<>();
        Map<Integer, Integer> cnt2 = new HashMap<>();
        for (int num : lst1) cnt1.put(num, cnt1.getOrDefault(num, 0) + 1);
        for (int num : lst2) cnt2.put(num, cnt2.getOrDefault(num, 0) + 1);

        // cnt 存储出现在两个数组中的元素及其最小出现次数
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int key : cnt1.keySet()) {
            if (cnt2.containsKey(key)) {
                cnt.put(key, Math.min(cnt1.get(key), cnt2.get(key)));
            }
        }

        // dic 以频次为键，将对应的元素放入列表中
        Map<Integer, List<Integer>> dic = new TreeMap<>();
        for (Map.Entry<Integer, Integer> entry : cnt.entrySet()) {
            int value = entry.getValue();
            dic.putIfAbsent(value, new ArrayList<>());
            dic.get(value).add(entry.getKey());
        }

    if (dic.isEmpty()) {
        System.out.println("NULL");
    } else {
        for (int k : dic.keySet()) {
            List<Integer> values = dic.get(k);
            Collections.sort(values);
            StringBuilder sb = new StringBuilder();
            sb.append(k).append(":");
            for (int i = 0; i < values.size(); i++) {
                if (i > 0) sb.append(",");
                sb.append(values.get(i));
            }
            System.out.println(sb.toString());
        }
    }

        scanner.close();
    }
}

C++

#include <iostream>
#include <sstream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

int main() {
    string line1, line2;
    getline(cin, line1);
    getline(cin, line2);

    vector<int> lst1, lst2;
    stringstream ss1(line1), ss2(line2);
    string temp;

    // 分割 lst1
    while (getline(ss1, temp, ',')) {
        lst1.push_back(stoi(temp));
    }
    // 分割 lst2
    while (getline(ss2, temp, ',')) {
        lst2.push_back(stoi(temp));
    }

    // cnt1 和 cnt2 用于记录各自列表中元素的频率
    map<int, int> cnt1, cnt2;
    for (int num : lst1) cnt1[num]++;
    for (int num : lst2) cnt2[num]++;

    // cnt 用于存储同时出现的元素，并取最小频率
    map<int, int> cnt;
    for (auto &p : cnt1) {
        int key = p.first;
        if (cnt2.count(key)) {
            cnt[key] = min(cnt1[key], cnt2[key]);
        }
    }

    // dic 以频率为 key，将元素存入对应列表
    map<int, vector<int>> dic;
    for (auto &p : cnt) {
        dic[p.second].push_back(p.first);
    }

    // 如果 dic 为空，输出 NULL
    if (dic.empty()) {
        cout << "NULL" << endl;
    } else {
        for (auto &p : dic) {
            int freq = p.first;
            vector<int> &vec = p.second;
            sort(vec.begin(), vec.end());
            cout << freq << ":";
            for (size_t i = 0; i < vec.size(); i++) {
                if (i > 0) cout << ",";
                cout << vec[i];
            }
            cout << endl;
        }
    }
    return 0;
}

C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_NUMS 20000
#define HASH_SIZE 65536

// 哈希表节点结构
typedef struct Node {
    int key;
    int count;
    struct Node* next;
} Node;

// 哈希表
Node* table1[HASH_SIZE];
Node* table2[HASH_SIZE];

// 结果结构体，用于保存频率和对应的数字集合
typedef struct {
    int freq;
    int values[MAX_NUMS];
    int count;
} Result;

Result results[MAX_NUMS];
int resultCount = 0;

// 简单哈希函数
unsigned int hash(int key) {
    return ((unsigned int)key) % HASH_SIZE;
}

// 插入或更新哈希表中某个 key 的计数
void insert(Node* table[], int key) {
    unsigned int h = hash(key);
    Node* curr = table[h];
    while (curr) {
        if (curr->key == key) {
            curr->count++;
            return;
        }
        curr = curr->next;
    }
    // 新建节点
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->key = key;
    newNode->count = 1;
    newNode->next = table[h];
    table[h] = newNode;
}

// 查找 key 是否存在于哈希表中，若存在返回计数，否则返回 0
int getCount(Node* table[], int key) {
    unsigned int h = hash(key);
    Node* curr = table[h];
    while (curr) {
        if (curr->key == key) return curr->count;
        curr = curr->next;
    }
    return 0;
}

// 在 results 中查找 freq，如果不存在则创建，返回索引
int getResultIndex(int freq) {
    for (int i = 0; i < resultCount; i++) {
        if (results[i].freq == freq) return i;
    }
    results[resultCount].freq = freq;
    results[resultCount].count = 0;
    return resultCount++;
}

// 比较函数用于排序
int compareInt(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int compareResult(const void* a, const void* b) {
    return ((Result*)a)->freq - ((Result*)b)->freq;
}

int main() {
    char line1[150000], line2[150000];
    fgets(line1, sizeof(line1), stdin);
    fgets(line2, sizeof(line2), stdin);

    int nums1[MAX_NUMS], nums2[MAX_NUMS];
    int n1 = 0, n2 = 0;

    // 解析第一行
    char* token = strtok(line1, ",\n");
    while (token) {
        nums1[n1++] = atoi(token);
        token = strtok(NULL, ",\n");
    }

    // 解析第二行
    token = strtok(line2, ",\n");
    while (token) {
        nums2[n2++] = atoi(token);
        token = strtok(NULL, ",\n");
    }

    // 填充哈希表
    for (int i = 0; i < n1; i++) insert(table1, nums1[i]);
    for (int i = 0; i < n2; i++) insert(table2, nums2[i]);

    // 查找两个表中都出现的元素并计算最小频率
    for (int i = 0; i < HASH_SIZE; i++) {
        Node* curr = table1[i];
        while (curr) {
            int key = curr->key;
            int count1 = curr->count;
            int count2 = getCount(table2, key);
            if (count2 > 0) {
                int minCount = count1 < count2 ? count1 : count2;
                int idx = getResultIndex(minCount);
                results[idx].values[results[idx].count++] = key;
            }
            curr = curr->next;
        }
    }

    if (resultCount == 0) {
        printf("NULL\n");
        return 0;
    }

    // 按频率排序输出
    qsort(results, resultCount, sizeof(Result), compareResult);
    for (int i = 0; i < resultCount; i++) {
        qsort(results[i].values, results[i].count, sizeof(int), compareInt);
        printf("%d:", results[i].freq);
        for (int j = 0; j < results[i].count; j++) {
            if (j > 0) printf(",");
            printf("%d", results[i].values[j]);
        }
        printf("\n");
    }
    return 0;
}

Node JavaScript

const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let lines = [];
rl.on('line', (line) => {
    lines.push(line.trim());
    if (lines.length === 2) {
        solve(lines[0], lines[1]);
        rl.close();
    }
});

function solve(line1, line2) {
    const lst1 = line1.split(',').map(Number);
    const lst2 = line2.split(',').map(Number);

    // 记录两个数组中的频率
    const cnt1 = {};
    const cnt2 = {};

    for (let num of lst1) cnt1[num] = (cnt1[num] || 0) + 1;
    for (let num of lst2) cnt2[num] = (cnt2[num] || 0) + 1;

    // 找出共有的元素及其最小频率
    const cnt = {};
    for (let key in cnt1) {
        if (key in cnt2) {
            const k = parseInt(key);
            cnt[k] = Math.min(cnt1[k], cnt2[k]);
        }
    }

    // dic: 频率 -> 元素数组
    const dic = {};
    for (let k in cnt) {
        const freq = cnt[k];
        if (!dic[freq]) dic[freq] = [];
        dic[freq].push(parseInt(k));
    }

    const keys = Object.keys(dic).map(Number).sort((a, b) => a - b);

    if (keys.length === 0) {
        console.log("NULL");
    } else {
        for (let freq of keys) {
            const values = dic[freq].sort((a, b) => a - b);
            console.log(`${freq}:${values.join(",")}`);
        }
    }
}

Go

package main

import (
        "bufio"
        "fmt"
        "os"
        "sort"
        "strconv"
        "strings"
)

func main() {
        scanner := bufio.NewScanner(os.Stdin)

        // 读取两行输入
        scanner.Scan()
        tokens1 := strings.Split(scanner.Text(), ",")
        scanner.Scan()
        tokens2 := strings.Split(scanner.Text(), ",")

        // 构建两个数组
        lst1 := make([]int, len(tokens1))
        lst2 := make([]int, len(tokens2))
        for i, v := range tokens1 {
                lst1[i], _ = strconv.Atoi(v)
        }
        for i, v := range tokens2 {
                lst2[i], _ = strconv.Atoi(v)
        }

        // cnt1 和 cnt2 记录出现频率
        cnt1 := map[int]int{}
        cnt2 := map[int]int{}
        for _, num := range lst1 {
                cnt1[num]++
        }
        for _, num := range lst2 {
                cnt2[num]++
        }

        // cnt 保存两个列表中都出现的元素和其最小频率
        cnt := map[int]int{}
        for k, v1 := range cnt1 {
                if v2, ok := cnt2[k]; ok {
                        if v1 < v2 {
                                cnt[k] = v1
                        } else {
                                cnt[k] = v2
                        }
                }
        }

        // dic 以频率为 key，值为相同频率的元素列表
        dic := map[int][]int{}
        for k, v := range cnt {
                dic[v] = append(dic[v], k)
        }

        if len(dic) == 0 {
                fmt.Println("NULL")
                return
        }

        // 对频率升序遍历
        freqs := []int{}
        for f := range dic {
                freqs = append(freqs, f)
        }
        sort.Ints(freqs)

        for _, f := range freqs {
                vals := dic[f]
                sort.Ints(vals)
                strs := []string{}
                for _, v := range vals {
                        strs = append(strs, strconv.Itoa(v))
                }
                fmt.Printf("%d:%s\n", f, strings.Join(strs, ","))
        }
}

时空复杂度

时间复杂度：O(N1+N2+NlogN+NMlogM)。构建cnt1和cnt2哈希表所需的时间复杂度为O(N1+N2)；N为dic的长度，对dic进行排序所需的时间复杂度为O(NlogN)；M为dic中最长的值列表的长度，其排序所需的时间复杂度为O(MlogM)，一共需要进行N次关于dic中的值列表的排序。

空间复杂度：O(N1+N2)。哈希表所需要的额外空间。