[数据结构与算法] Leetcode——349. 两个数组的交集/350. 两个数组的交集 II

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> Leetcode——349. 两个数组的交集/350. 两个数组的交集 II -> 正文阅读

[数据结构与算法]Leetcode——349. 两个数组的交集/350. 两个数组的交集 II

概述

分析

349

题目要求寻找带个数组中元素的交集，并且最后输出唯一的值
此题的交集才真正的符合数学上的交集
同样，可以使用哈希表统计

350

350和349的区别在于最终返回的结果要输出重复元素在两个数组中出现的最少次数
可以和349一样使用哈希表来确定重复的元素，但是key对应的value的赋值应该有所不同

思路

代码

349

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        int hash_table[1005] = {0};			// 1005是题目限制的元素的最大值
        for (auto num : nums1)
            hash_table[num] = 1;			// 统计，注意这里直接赋值1，因为该哈希的key值只需要
        
        vector<int> result;
        for (auto num : nums2)
            if (--hash_table[num] >= 0)  result.push_back(num);		// 统计

        return result;
    }
};

350

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int,int> unordered_map_int_to_int;
        for (auto num : nums1)
            ++unordered_map_int_to_int[num];		// 这里要统计元素出现的次数
        
        vector<int> result;
        for (auto num : nums2) {
            if (unordered_map_int_to_int[num]-- > 0)	// 判断>0,可以确保元素加入的次数是在两个数组中 
                result.emplace_back(num);			// 重复出现的元素要多次加入结果
        }
        return result;
    }
};