leetcode 349 两个数组的交集

简介: leetcode 349 两个数组的交集

两个数组的交集


f5ea230726484a74b529aba7a644b71e.png

数组哈希表

建立两个1000大小数组,暴力映射进去。

消耗空间过大。

#include <iostream>
#include<string>
#include<vector>
using namespace std;
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        vector<int>record1(1000, 0);
        vector<int>record2(1000, 0);
        for (int i = 0; i < nums1.size(); i++)
        {
            record1[nums1[i]]++;
        }
        for (int i = 0; i < nums2.size(); i++)
        {
            record2[nums2[i]]++;
        }
        vector<int>record3;
        for (int i = 0; i < 1000; i++)
        {
            if (record1[i] != 0 && record2[i] != 0) record3.push_back(i);
        }
        return record3;
    }
};
int main()
{
    vector<int> nums1 = { 4,9,5 };
    vector<int> nums2 = { 9,4,9,8,4 };
    Solution a;
    vector<int> nums3 = a.intersection(nums1, nums2);
    for(int i = 0 ;i<nums3.size();i++)
    cout <<nums3[i]<<' ';
    cout << endl;
  return 0;
}

set哈希表

使用unordered_set进行哈希映射,统计数组出现的元素

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> result;
        unordered_set<int> set1(nums1.begin() , nums1.end());
        for (int i = 0; i < nums2.size(); i++)
        {
            if (set1.find(nums2[i]) != set1.end()) 
            {
                result.insert(nums2[i]);
            }
        }
        return vector<int>(result.begin(), result.end());
    }
};

C++11写法 auto关键字

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> result;
        unordered_set<int> set1(nums1.begin() , nums1.end());
        for (auto num : nums2)
        {
            if (set1.find(num) != set1.end()) 
            {
                result.insert(num);
            }
        }
        return vector<int>(result.begin(), result.end());
    }
};


二刷

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        set<int> my_set;
        vector<int> result;
        for(int i=0 ;i<nums1.size();i++)
            my_set.insert(nums1[i]);
        for(int i=0 ;i<nums2.size();i++)
        {
            if(my_set.find(nums2[i]) != my_set.end())
            {
                 my_set.erase(nums2[i]);
                result.push_back(nums2[i]);
            }
        }
        return result;
    }
};

相关文章
|
2月前
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
40 0
|
4月前
|
算法
LeetCode第53题最大子数组和
LeetCode第53题"最大子数组和"的解题方法,利用动态规划思想,通过一次遍历数组,维护到当前元素为止的最大子数组和,有效避免了复杂度更高的暴力解法。
LeetCode第53题最大子数组和
LeetCode------找到所有数组中消失的数字(6)【数组】
这篇文章介绍了LeetCode上的"找到所有数组中消失的数字"问题,提供了一种解法,通过两次遍历来找出所有未在数组中出现的数字:第一次遍历将数组中的每个数字对应位置的值增加数组长度,第二次遍历找出所有未被增加的数字,即缺失的数字。
|
2月前
【LeetCode-每日一题】 删除排序数组中的重复项
【LeetCode-每日一题】 删除排序数组中的重复项
21 4
|
2月前
|
索引
Leetcode第三十三题(搜索旋转排序数组)
这篇文章介绍了解决LeetCode第33题“搜索旋转排序数组”的方法,该问题要求在旋转过的升序数组中找到给定目标值的索引,如果存在则返回索引,否则返回-1,文章提供了一个时间复杂度为O(logn)的二分搜索算法实现。
19 0
Leetcode第三十三题(搜索旋转排序数组)
|
2月前
|
算法 C++
Leetcode第53题(最大子数组和)
这篇文章介绍了LeetCode第53题“最大子数组和”的动态规划解法,提供了详细的状态转移方程和C++代码实现,并讨论了其他算法如贪心、分治、改进动态规划和分块累计法。
68 0
|
2月前
|
C++
【LeetCode 12】349.两个数组的交集
【LeetCode 12】349.两个数组的交集
17 0
|
4月前
|
算法
LeetCode第81题搜索旋转排序数组 II
文章讲解了LeetCode第81题"搜索旋转排序数组 II"的解法,通过二分查找算法并加入去重逻辑来解决在旋转且含有重复元素的数组中搜索特定值的问题。
LeetCode第81题搜索旋转排序数组 II
|
4月前
|
算法 索引
LeetCode第34题在排序数组中查找元素的第一个和最后一个位置
这篇文章介绍了LeetCode第34题"在排序数组中查找元素的第一个和最后一个位置"的解题方法,通过使用双指针法从数组两端向中间同时查找目标值,有效地找到了目标值的首次和最后一次出现的索引位置。
LeetCode第34题在排序数组中查找元素的第一个和最后一个位置
|
4月前
|
算法
LeetCode第33题搜索旋转排序数组
这篇文章介绍了LeetCode第33题"搜索旋转排序数组"的解题方法,通过使用二分查找法并根据数组的有序性质调整搜索范围,实现了时间复杂度为O(log n)的高效搜索算法。
LeetCode第33题搜索旋转排序数组