LeetCode 350. 两个数组的交集 II C/C++/Python

简介: LeetCode 350. 两个数组的交集 II C/C++/Python

题目描述

给你两个整数数组 nums1nums2 ,请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数,应与元素在两个数组中都出现的次数一致(如果出现次数不一致,则考虑取较小值)。可以不考虑输出结果的顺序。

示例 1:

输入:nums1 = [1,2,2,1], nums2 = [2,2]
输出:[2,2]

示例 2:

输入:nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出:[4,9]

提示:

  • 1 <= nums1.length, nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 1000

使用哈希进行求解。

C语言版

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int _callback(const void* val1, const void* val2)
{
  return *(int*)val1 - *(int*)val2;
}
int* intersect(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
  int index1 = 0, index2 = 0;
  qsort(nums1, nums1Size, sizeof(nums1[0]), _callback);
  qsort(nums2, nums2Size, sizeof(nums2[0]), _callback);
  *returnSize = 0;
  int* ret = (int*)malloc(sizeof(int) * fmin(nums1Size, nums2Size));
  while (index1 < nums1Size && index2 < nums2Size)
  {
    if (nums1[index1] < nums2[index2])
    {
      index1++; /*如果nums1中的数据小,那么nums1的游标下移*/
    }
    else if (nums1[index1] > nums2[index2])
    {
      index2++; /*如果nums2中的数据小,那么nums2的游标下移*/
    }
    else
    {
      *(ret + (*returnSize)) = nums1[index1]; /*两个数相等则加入容器*/
      index1++;
      index2++;
      (*returnSize)++;
    }
  }
  return ret;
}

C++版

class Solution {
public:
  vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
    unordered_map<int, int> flag;
    vector<int> ret;
    for (vector<int>::iterator it = nums1.begin(); it != nums1.end(); it++)
    {
      if (flag.find(*it) == flag.end())
      {
        flag.insert(make_pair(*it, 1));
      }
      else
      {
        flag[*it]++;
      }
    }
    for (vector<int>::iterator it = nums2.begin(); it != nums2.end(); it++)
    {
      if (flag.find(*it) != flag.end())
      {
        if (flag[*it] > 0)
        {
          ret.push_back(*it);
          flag[*it]--;
        }
      }
    }
        return ret;
  }
};

Python版

#使用哈希记录nums1元素及元素出现的次数,并在nums2中找同时出现的元素存入列表
#时间复杂度   O(m+n)
class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        hashmap = {}
        ret = []
        if len(nums1) > len(nums2):
            return self.intersect(nums2, nums1)
        for i in nums1:
            if hashmap.get(i) == None:
                hashmap[i] = 1
            else:
                hashmap[i] += 1
        for i in nums2:
            if hashmap.get(i) != None:
                if hashmap[i] > 0:
                    ret.append(i)
                    hashmap[i] -= 1
        return ret


相关文章
从集思录可转债数据探秘:Python与C++实现的移动平均算法应用
本文探讨了如何利用移动平均算法分析集思录提供的可转债数据,帮助投资者把握价格趋势。通过Python和C++两种编程语言实现简单移动平均(SMA),展示了数据处理的具体方法。Python代码借助`pandas`库轻松计算5日SMA,而C++代码则通过高效的数据处理展示了SMA的计算过程。集思录平台提供了详尽且及时的可转债数据,助力投资者结合算法与社区讨论,做出更明智的投资决策。掌握这些工具和技术,有助于在复杂多变的金融市场中挖掘更多价值。
27 12
【C++核心】特殊的元素集合-数组与字符串详解
这篇文章详细讲解了C++中数组和字符串的基本概念、操作和应用,包括一维数组、二维数组的定义和使用,以及C风格字符串和C++字符串类的对比。
117 4
【C++面向对象——群体类和群体数据的组织】实现含排序功能的数组类(头歌实践教学平台习题)【合集】
1. **相关排序和查找算法的原理**:介绍直接插入排序、直接选择排序、冒泡排序和顺序查找的基本原理及其实现代码。 2. **C++ 类与成员函数的定义**:讲解如何定义`Array`类,包括类的声明和实现,以及成员函数的定义与调用。 3. **数组作为类的成员变量的处理**:探讨内存管理和正确访问数组元素的方法,确保在类中正确使用动态分配的数组。 4. **函数参数传递与返回值处理**:解释排序和查找函数的参数传递方式及返回值处理,确保函数功能正确实现。 通过掌握这些知识,可以顺利地将排序和查找算法封装到`Array`类中,并进行测试验证。编程要求是在右侧编辑器补充代码以实现三种排序算法
46 5
根据相机旋转矩阵求解三个轴的旋转角/欧拉角/姿态角 或 旋转矩阵与欧拉角(Euler Angles)之间的相互转换,以及python和C++代码实现
根据相机旋转矩阵求解三个轴的旋转角/欧拉角/姿态角 或 旋转矩阵与欧拉角(Euler Angles)之间的相互转换,以及python和C++代码实现
500 0
|
4月前
|
探索Python与C/C++混合编程的艺术
探索Python与C/C++混合编程的艺术
94 1
|
5月前
|
C++
C++(十一)对象数组
本文介绍了C++中对象数组的使用方法及其注意事项。通过示例展示了如何定义和初始化对象数组,并解释了栈对象数组与堆对象数组在初始化时的区别。重点强调了构造器设计时应考虑无参构造器的重要性,以及在需要进一步初始化的情况下采用二段式初始化策略的应用场景。
为什么Python比C++慢很多?
Python相较于C++较慢主要体现在:动态类型系统导致运行时需解析类型,增加开销;作为解释型语言,逐行转换字节码的过程延长了执行时间;自动内存管理和垃圾回收机制虽简化操作但也带来了额外负担;全局解释器锁(GIL)限制了多线程性能;尽管Python库方便灵活,但在性能上往往不及C++底层库。然而,Python在某些领域如数据分析、机器学习中,凭借其高级别抽象和简洁语法仍表现出色。选语言需依据具体应用场景和需求综合考量。
WK
141 1
|
6月前
|
右手坐标系,空间点绕轴旋转公式&程序(Python和C++程序)
右手坐标系,空间点绕轴旋转公式&程序(Python和C++程序)
162 0
|
6月前
|
C++数组、vector求最大值最小值及其下标
C++数组、vector求最大值最小值及其下标
226 0
「只出现一次的数字」python之leetcode刷题|007
题目 给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现了三次。找出那个只出现了一次的元素。 说明: 你的算法应该具有线性时间复杂度。
1506 0

热门文章

最新文章