数组的交集——倒排索引查询,因为不重复,还是可以采用计数的思路做,外部排序,二路归并的做法也不错
2023-09-14 09:11:49 时间
793. 多个数组的交集
中文
English
给出多个数组,求它们的交集。输出他们交集的大小。
样例
样例 1:
输入: [[1,2,3],[3,4,5],[3,9,10]]
输出: 1
解释:
只有3出现在三个数组中。
样例 2:
输入: [[1,2,3,4],[1,2,5,6,7][9,10,1,5,2,3]]
输出: 2
解释:
交集是[1,2].
注意事项
- 输入的所有数组元素总数不超过
500000
。 - 题目数据每个数组里的元素没有重复。
import heapq class Solution: """ @param arrs: the arrays @return: the number of the intersection of the arrays """ def intersectionOfArrays(self, arrs): # write your code here q = [] for i, arr in enumerate(arrs): if arr: arr.sort() heapq.heappush(q, (arrs[i][0], i, 0)) ans = 0 prev = float('inf') cnt = 1 while q: val, i, j = heapq.heappop(q) if val == prev: cnt += 1 if cnt == len(arrs): ans += 1 else: prev = val cnt = 1 if j+1 < len(arrs[i]): heapq.heappush(q, (arrs[i][j+1], i, j+1)) return ans
此外,还可以使用 二路归并的做法:
import heapq class Solution: """ @param arrs: the arrays @return: the number of the intersection of the arrays """ def intersectionOfArrays(self, arrs): # write your code here def intersect2(arr1, arr2): return list(set(arr1) & set(arr2)) def intersect(arr, l, r): if l == r: return arr[l] if l > r: return [] mid = (l+r) >> 1 arr1 = intersect(arr, l, mid) arr2 = intersect(arr, mid+1, r) return intersect2(arr1, arr2) return len(intersect(arrs, 0, len(arrs)-1))
相关文章
- [博客搭建] 通过用户邮箱认证来介绍 django-allauth 的使用思路
- java在Socket传输中文乱码解决思路及代码「建议收藏」
- Angular HTTP 请求自定义 timeout 值的一种实现思路
- 数学知识——博弈论(巴什博奕、尼姆博奕、威佐夫博奕)思路及例题「建议收藏」
- 编写一个爬虫的思路,当遇到反爬时如何处理
- pop_master的花式解题思路
- Sql Server 死锁的监控分析解决思路
- 查询高效查询Oracle大表:优化关联查询思路(oracle大表关联)
- HUD换个思路便柳暗花明
- Linux下浏览器开发新思路(linux浏览器开发)
- 物联网Cat.1芯片上区块链,打开了数字新基建的思路
- Oracle数据库全量注释极致编程思路(oracle全量注释)
- 区块链研习 | 利用经济模型应对联盟链攻击的两种思路
- PHP中的session永不过期的解决思路及实现方法分享
- Android使用Intent传递数据的实现思路与代码
- 点击页面其它地方隐藏该div的两种思路
- js拖拽一些常见的思路方法整理
- php+ajax实现带进度条的大数据排队导出思路以及源码