【Leetcode 349，350】两个数组的交集，两个数组的交集II，超长数组求交集，有序数组求交集

2024-05-28 13:18
文章标签 leetcode 数组 有序 ii 两个 350 交集 超长 349

本文主要是介绍【Leetcode 349，350】两个数组的交集，两个数组的交集II，超长数组求交集，有序数组求交集，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述

两个数组的交集（Leetcode 349）

方法一 两个集合

在这里插入图片描述
python版本

class Solution:def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:set1 = set(nums1)set2 = set(nums2)return self.set_intersection(set1, set2)def set_intersection(self, set1, set2):if len(set1) > len(set2):return self.set_intersection(set2, set1)return [x for x in set1 if x in set2]

java版本

class Solution {public int[] intersection(int[] nums1, int[] nums2) {Set<Integer> set1 = new HashSet<Integer>();Set<Integer> set2 = new HashSet<Integer>();for (int num : nums1) {set1.add(num);}for (int num : nums2) {set2.add(num);}return getIntersection(set1, set2);}public int[] getIntersection(Set<Integer> set1, Set<Integer> set2) {if (set1.size() > set2.size()) {return getIntersection(set2, set1);}Set<Integer> intersectionSet = new HashSet<Integer>();for (int num : set1) {if (set2.contains(num)) {intersectionSet.add(num);}}int[] intersection = new int[intersectionSet.size()];int index = 0;for (int num : intersectionSet) {intersection[index++] = num;}return intersection;}
}

在这里插入图片描述

方法二 排序+双指针

在这里插入图片描述
java版本

class Solution {public int[] intersection(int[] nums1, int[] nums2) {Arrays.sort(nums1);Arrays.sort(nums2);int length1 = nums1.length, length2 = nums2.length;int[] intersection = new int[length1 + length2];int index = 0, index1 = 0, index2 = 0;while (index1 < length1 && index2 < length2) {int num1 = nums1[index1], num2 = nums2[index2];if (num1 == num2) {// 保证加入元素的唯一性if (index == 0 || num1 != intersection[index - 1]) {intersection[index++] = num1;}index1++;index2++;} else if (num1 < num2) {index1++;} else {index2++;}}return Arrays.copyOfRange(intersection, 0, index);}
}

python版本

class Solution:def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:nums1.sort()nums2.sort()length1, length2 = len(nums1), len(nums2)intersection = list()index1 = index2 = 0while index1 < length1 and index2 < length2:num1 = nums1[index1]num2 = nums2[index2]if num1 == num2:# 保证加入元素的唯一性if not intersection or num1 != intersection[-1]:intersection.append(num1)index1 += 1index2 += 1elif num1 < num2:index1 += 1else:index2 += 1return intersection

在这里插入图片描述
https://leetcode-cn.com/problems/intersection-of-two-arrays

两个数组的交集II（Leetcode 350）

在这里插入图片描述
在这里插入图片描述

方法一：哈希表

在这里插入图片描述

java版本

class Solution {public int[] intersect(int[] nums1, int[] nums2) {if (nums1.length > nums2.length) {return intersect(nums2, nums1);}Map<Integer, Integer> map = new HashMap<Integer, Integer>();for (int num : nums1) {int count = map.getOrDefault(num, 0) + 1;map.put(num, count);}int[] intersection = new int[nums1.length];int index = 0;for (int num : nums2) {int count = map.getOrDefault(num, 0);if (count > 0) {intersection[index++] = num;count--;if (count > 0) {map.put(num, count);} else {map.remove(num);}}}return Arrays.copyOfRange(intersection, 0, index);}
}

python版本

class Solution:def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:if len(nums1) > len(nums2):return self.intersect(nums2, nums1)m = collections.Counter()for num in nums1:m[num] += 1intersection = list()for num in nums2:if (count := m.get(num, 0)) > 0:intersection.append(num)m[num] -= 1if m[num] == 0:m.pop(num)return intersection

在这里插入图片描述

方法二：排序

在这里插入图片描述
python版本

class Solution:def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:nums1.sort()nums2.sort()length1, length2 = len(nums1), len(nums2)intersection = list()index1 = index2 = 0while index1 < length1 and index2 < length2:if nums1[index1] < nums2[index2]:index1 += 1elif nums1[index1] > nums2[index2]:index2 += 1else:intersection.append(nums1[index1])index1 += 1index2 += 1return intersection

java版本

class Solution {public int[] intersect(int[] nums1, int[] nums2) {Arrays.sort(nums1);Arrays.sort(nums2);int length1 = nums1.length, length2 = nums2.length;int[] intersection = new int[Math.min(length1, length2)];int index1 = 0, index2 = 0, index = 0;while (index1 < length1 && index2 < length2) {if (nums1[index1] < nums2[index2]) {index1++;} else if (nums1[index1] > nums2[index2]) {index2++;} else {intersection[index] = nums1[index1];index1++;index2++;index++;}}return Arrays.copyOfRange(intersection, 0, index);}
}

在这里插入图片描述
https://leetcode-cn.com/problems/intersection-of-two-arrays-ii

超长数组求交集

在这里插入图片描述
方法一 ：利用python的counter函数

from collections import Counterc = Counter([1,2,3])
d = Counter([2,3,4])
res= c&d
print(list(res))

更多用法

>>> c = Counter()                           # 创建一个新的空counter
>>> c = Counter('abcasdf')                  # 一个迭代对象生成的counter
>>> c = Counter({'red': 4, 'yello': 2})      # 一个映射生成的counter
>>> c = Counter(cats=2, dogs=5)             # 关键字参数生成的counter# counter 生成counter, 虽然这里并没有什么用
>>> from collections import Counter
>>> c = Counter('abcasd')
>>> c
Counter({'a': 2, 'c': 1, 'b': 1, 's': 1, 'd': 1})
>>> c2 = Counter(c)
>>> c2
Counter({'a': 2, 'c': 1, 'b': 1, 's': 1, 'd': 1})

因为 Counter 实现了字典的 missing 方法， 所以当访问不存在的key的时候，返回值为0:

>>> c = Counter(['apple', 'pear'])
>>> c['orange']
0

counter 常用的方法：

# elements() 按照counter的计数，重复返回元素
>>> c = Counter(a=4, b=2, c=0, d=-2)
>>> list(c.elements())
['a', 'a', 'a', 'a', 'b', 'b']# most_common(n) 按照counter的计数，按照降序，返回前n项组成的list; n忽略时返回全部
>>> Counter('abracadabra').most_common(3)
[('a', 5), ('r', 2), ('b', 2)]# subtract([iterable-or-mapping]) counter按照相应的元素，计数相减
>>> c = Counter(a=4, b=2, c=0, d=-2)
>>> d = Counter(a=1, b=2, c=3, d=4)
>>> c.subtract(d)
>>> c
Counter({'a': 3, 'b': 0, 'c': -3, 'd': -6})# update([iterable-or-mapping]) 不同于字典的update方法，这里更新counter时，相同的key的value值相加而不是覆盖
# 实例化 Counter 时， 实际也是调用这个方法# Counter 间的数学集合操作
>>> c = Counter(a=3, b=1, c=5)
>>> d = Counter(a=1, b=2, d=4)
>>> c + d                       # counter相加, 相同的key的value相加
Counter({'c': 5, 'a': 4, 'd': 4, 'b': 3})
>>> c - d                       # counter相减, 相同的key的value相减，只保留正值得value
Counter({'c': 5, 'a': 2})
>>> c & d                       # 交集:  取两者都有的key,value取小的那一个
Counter({'a': 1, 'b': 1})
>>> c | d                       # 并集:  汇聚所有的key, key相同的情况下，取大的value
Counter({'c': 5, 'd': 4, 'a': 3, 'b': 2})
常见做法:
sum(c.values())                 # 继承自字典的.values()方法返回values的列表，再求和
c.clear()                       # 继承自字典的.clear()方法，清空counter
list(c)                         # 返回key组成的list
set(c)                          # 返回key组成的set
dict(c)                         # 转化成字典
c.items()                       # 转化成(元素，计数值)组成的列表
Counter(dict(list_of_pairs))    # 从(元素，计数值)组成的列表转化成Counter
c.most_common()[:-n-1:-1]       # 最小n个计数的(元素，计数值)组成的列表
c += Counter()                  # 利用counter的相加来去除负值和0的值

https://www.zhihu.com/question/420013804
https://blog.csdn.net/jason3586596/article/details/80073517

方法二：位图法

     BitSet bits1 = new BitSet(16);BitSet bits2 = new BitSet(16);// set some bitsfor(int i=0; i<16; i++) {if((i%2) == 0) bits1.set(i);if((i%5) != 0) bits2.set(i);}System.out.println("Initial pattern in bits1: ");System.out.println(bits1);System.out.println("\nInitial pattern in bits2: ");System.out.println(bits2);//AND bitsbits2.and(bits1);System.out.println("\nbits2 AND bits1: ");System.out.println(bits2);

方法三：排序法
先把两个数组给排序，再用双指针，可以见下面

方法四：索引法

以空间换时间，把集合(感谢网友的指正，集合里面的元素是不重复的！)中的元素作为数组下表的索引。来看例子：

A= {1 ,12, 13, 25}，那Asub[1] = 3,Asub[12] = 1 ,Asub[13] = 1 ,Asub[25] = 1 ;

B=｛1, 2, 3, 15 ,｝那Bsub[1] = 1; Bsub[2] = 1; Bsub[3] = 1; Bsub[15] = 1;

对元素少的集合扫一遍，发现Asub[1] = 3 和Bsub[1] = 1有相同的索引1，并且重复度为1（因为一个集合当中没有重复元素），所以交集肯定包括{1, 1}; Bsub[2] = 1而Asub[2] = 0，表示无交集，依次类推，可以得到集合A和B的交集。

假设集合中存在负数，可以把集合分成正整数和负整数（加个负号变正整数）两部分，解法同上！

优点：速度快，时间复杂度O(N)

缺点：空间消耗大，以空间换取时间

这是我看到题目第一个想到的算法，再来想到排序法，而集合压缩是有感而发的，索引法的缺点是空间消耗多，原因是可能索引值太大，要申请很多的不必要的空间，这个缺点也是有克服的方法的，就是采用哈希查找，找到一个比较合适的哈希函数，把索引的值减小了，从而减少消耗的内存空间。比如哈希函数为f(x) = (x + MOD) % MOD （除留余数法，MOD为常数），还有平方取中法、折叠法等方法，然而，无论哈希函数设计有多么精细，都会产生冲突现象，也就是2个关键字处理函数的结果映射在了同一位置上，因此，有一些方法可以避免冲突。这里没有仔细钻研，只提供一些思路，有兴趣的朋友可以继续研究。

code：（我的代码仅适用与正整数部分，未处理负数）

C++代码

/*Tencent: A、B两个整数集合，设计一个算法求他们的交集，尽可能的高效
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define M 6
#define N 5
int Mymin(int a, int b)
{return a < b ? a : b;
}
int main(void)
{int A[] = {1, 10, 12, 23, 5, 45};int B[] = {1, 10, 12, 123, 52};//find MaxNumber in Aint ifindA = 0;int MaxInA = A[0];for(ifindA = 0; ifindA < M; ifindA++){MaxInA = MaxInA > A[ifindA] ? MaxInA : A[ifindA];}//find MaxNumber in Bint ifindB = 0;int MaxInB = 0;for(ifindB = 0; ifindB < M; ifindB++){MaxInB = MaxInB > A[ifindB] ? MaxInB : A[ifindB];}int *AsubPositive = (int *)malloc(sizeof(int) * (MaxInA + 1));int *BsubPositive = (int *)malloc(sizeof(int) * (MaxInB + 1));memset(AsubPositive, 0, sizeof(int) * (MaxInA + 1));memset(BsubPositive, 0, sizeof(int) * (MaxInB + 1));//COPY Positive and Negative numbers of Aint i = 0;for(i = 0; i < M; i++){AsubPositive[A[i]]++;}//COPY Positive and Negative numbers of Bint j = 0;for(j = 0; j < N; j++){BsubPositive[B[j]]++;}int  k = 0;int icount = 0;//扫描AsubNegative和BsubPositiveprintf("the Intersection of A and B is : { ");for(k = 0; k < M; k++){//有交集输出该数icount = Mymin(AsubPositive[A[k]], BsubPositive[A[k]]);if(icount == 1){printf("%-3d",A[k]);}A[k] = 0;}printf(" }");return 0;
}

方法五：压缩集合法

见https://blog.csdn.net/jie1991liu/article/details/13168255

https://www.nowcoder.com/questionTerminal/6245d7bcae414235ab682b3f842d76bc?orderByHotValue=0&pos=159&mutiTagIds=578
https://blog.csdn.net/moli152_/article/details/48163351
https://blog.csdn.net/jie1991liu/article/details/13168255

有序数组求交集

方法一：如果可以输入重复的数字
输入：l1 = [1,3,4,5,7]
l2 = [2,5,6,7,9]
输出：[5,7]

def comNumber(l1,l2):i=0j=0res = []while i < len(l1) and j < len(l2):if l1[i] == l2[j]:res.append(l1[i])i+=1j+=1elif l1[i]<l2[j]:i+=1else:j+=1return resif __name__ == '__main__':l1 = [1,3,4,5,2,4,1,7]l2 = [2,5,2,6,7,9]b=comNumber(l1,l2)print(b)

方法二：不能输出重复的数字

思路：

双指针：p1指向arr1的开头，p2指向arr2的开头，然后进行比较，如果p1与p2指向的数相等，则将这个数加入结果集。然后p1++,p2++，再继续遍历。如果p1指向的数小于p2指向的数，则p1++，否则p2++；

实现：要求结果中不含重复的数，则选用TreeSet而不用ArrayList

public TreeSet<Integer> find(int[] arr1,int[] arr2){TreeSet<Integer> set=new TreeSet<>();int p1=0;int p2=0;while(p1<arr1.length&&p2<arr2.length){if(arr1[p1]==arr2[p2]){set.add(arr1[p1]);p1++;p2++;}else if(arr1[p1]<arr2[p2]){p1++;}else{p2++;}}return set;		
}

https://blog.csdn.net/weixin_40924580/article/details/84351584
https://blog.csdn.net/orangefly0214/article/details/89390586

这篇关于【Leetcode 349，350】两个数组的交集，两个数组的交集II，超长数组求交集，有序数组求交集的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1010672。

相关文章

C++初始化数组的几种常见方法(简单易懂)

C++初始化数组的几种常见方法(简单易懂)

《C++初始化数组的几种常见方法(简单易懂)》本文介绍了C++中数组的初始化方法,包括一维数组和二维数组的初始化,以及用new动态初始化数组,在C++11及以上版本中,还提供了使用std::array... 目录1、初始化一维数组1.1、使用列表初始化（推荐方式）1.2、初始化部分列表1.3、使用std::
阅读更多...
C++ Primer 多维数组的使用

C++ Primer 多维数组的使用

《C++Primer多维数组的使用》本文主要介绍了多维数组在C++语言中的定义、初始化、下标引用以及使用范围for语句处理多维数组的方法,具有一定的参考价值,感兴趣的可以了解一下... 目录多维数组多维数组的初始化多维数组的下标引用使用范围for语句处理多维数组指针和多维数组多维数组严格来说,C++语言没
阅读更多...
Python如何计算两个不同类型列表的相似度

Python如何计算两个不同类型列表的相似度

《Python如何计算两个不同类型列表的相似度》在编程中,经常需要比较两个列表的相似度,尤其是当这两个列表包含不同类型的元素时,下面小编就来讲讲如何使用Python计算两个不同类型列表的相似度吧... 目录摘要引言数字类型相似度欧几里得距离曼哈顿距离字符串类型相似度Levenshtein距离Jaccard相
阅读更多...
使用Navicat工具比对两个数据库所有表结构的差异案例详解

使用Navicat工具比对两个数据库所有表结构的差异案例详解

《使用Navicat工具比对两个数据库所有表结构的差异案例详解》：本文主要介绍如何使用Navicat工具对比两个数据库test_old和test_new,并生成相应的DDLSQL语句,以便将te... 目录概要案例一、如图两个数据库test_old和test_new进行比较：二、开始比较总结概要公司存在多
阅读更多...
C#比较两个List集合内容是否相同的几种方法

C#比较两个List集合内容是否相同的几种方法

《C#比较两个List集合内容是否相同的几种方法》本文详细介绍了在C#中比较两个List集合内容是否相同的方法,包括非自定义类和自定义类的元素比较,对于非自定义类,可以使用SequenceEqual、... 目录 一、非自定义类的元素比较1. 使用 SequenceEqual 方法（顺序和内容都相等）2.
阅读更多...
Java 字符数组转字符串的常用方法

Java 字符数组转字符串的常用方法

《Java字符数组转字符串的常用方法》文章总结了在Java中将字符数组转换为字符串的几种常用方法,包括使用String构造函数、String.valueOf()方法、StringBuilder以及A... 目录1. 使用String构造函数1.1 基本转换方法1.2 注意事项2. 使用String.valu
阅读更多...
JAVA中整型数组、字符串数组、整型数和字符串 的创建与转换的方法

JAVA中整型数组、字符串数组、整型数和字符串 的创建与转换的方法

《JAVA中整型数组、字符串数组、整型数和字符串的创建与转换的方法》本文介绍了Java中字符串、字符数组和整型数组的创建方法,以及它们之间的转换方法,还详细讲解了字符串中的一些常用方法,如index... 目录一、字符串、字符数组和整型数组的创建1、字符串的创建方法1.1 通过引用字符数组来创建字符串1.2
阅读更多...
锐捷和腾达哪个好? 两个品牌路由器对比分析

锐捷和腾达哪个好? 两个品牌路由器对比分析

《锐捷和腾达哪个好?两个品牌路由器对比分析》在选择路由器时，Tenda和锐捷都是备受关注的品牌，各自有独特的产品特点和市场定位，选择哪个品牌的路由器更合适，实际上取决于你的具体需求和使用场景，我们从... 在选购路由器时，锐捷和腾达都是市场上备受关注的品牌，但它们的定位和特点却有所不同。锐捷更偏向企业级和专
阅读更多...
基于Redis有序集合实现滑动窗口限流的步骤

基于Redis有序集合实现滑动窗口限流的步骤

《基于Redis有序集合实现滑动窗口限流的步骤》滑动窗口算法是一种基于时间窗口的限流算法,通过动态地滑动窗口,可以动态调整限流的速率,Redis有序集合可以用来实现滑动窗口限流,本文介绍基于Redis... 滑动窗口算法是一种基于时间窗口的限流算法，它将时间划分为若干个固定大小的窗口，每个窗口内记录了该时间
阅读更多...
vue如何监听对象或者数组某个属性的变化详解

vue如何监听对象或者数组某个属性的变化详解

《vue如何监听对象或者数组某个属性的变化详解》这篇文章主要给大家介绍了关于vue如何监听对象或者数组某个属性的变化,在Vue.js中可以通过watch监听属性变化并动态修改其他属性的值,watch通... 目录前言用watch监听深度监听使用计算属性watch和计算属性的区别在vue 3中使用watchE
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2