Intersection of Two Arrays（交集）
2024-09-05 18:55:32
来源：https://leetcode.com/problems/intersection-of-two-arrays
Given two arrays, write a function to compute their intersection.
Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].
Note:
- Each element in the result must be unique.
- The result can be in any order.
1. 直接使用HashSet
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> set = new HashSet<>();
Set<Integer> intersect = new HashSet<>();
for(int i=0; i<nums1.length; i++) {
set.add(nums1[i]);
}
for(int i=0; i<nums2.length; i++) {
if(set.contains(nums2[i])) {
intersect.add(nums2[i]);
}
}
int[] result = new int[intersect.size()];
int i = 0;
for(Integer num: intersect) {
result[i++] = num;
}
return result;
}
}// 6 ms
2. 类似BitMap的思想，LeetCode 1ms sample，缺点是数组中的元素不能为负数……
（1）求出两个数组的最大值
（2）建立 长度=最大值+1 的数组A，假设数组的索引为i，那么A[i]的值表示i是否在两个数组中存在，若为0表示不存在于任何一个数组中，为1表示存在于第一个数组中，为2表示两个数组中都存在
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
int max = 0;
for(int num: nums1) {
if(num > max) {
max = num;
}
}
for(int num: nums2) {
if(num > max) {
max = num;
}
}
int[] indexMap = new int[max+1];
for(int num: nums1) {
indexMap[num] = 1;
}
int cnt = 0;
for(int num: nums2) {
if(indexMap[num] == 1) {
indexMap[num] = 2;
cnt++;
}
}
int[] result = new int[cnt];
for(int i=0; i<max+1; i++) {
if(indexMap[i] == 2) {
result[--cnt] = i;
}
}
return result;
}
}
最新文章
- 用collectionview实现瀑布流-转(后面附demo，供参考)
- sql
- Linux 循环
- 纸上谈兵：哈希表（hash table）
- 41.Android之图片放大缩小学习
- Ultra Edit常用正则表达式
- 个人笔记--Servlet之过滤器实现权限拦截
- bzoj 2852: 强大的区间 辗转相除
- （转）javascript组件开发方式
- 浅谈Spring(一)
- Linux基础正则表达式:grep,sed
- C各个类型的大小
- 漫谈Java IO之基础篇
- 实验二《Java面向对象程序设计》实验报告
- 2018年12月8日广州.NET微软技术俱乐部活动总结
- Revit二次开发： 文件损坏
- Leetcode 215. 数组中的第K个最大元素 By Python
- Sql批量修改帝国cms文章发布时间(需unix时间,否则会变为1970-01-01)
- php isset+{} 判断字符串长度比strlen效率高
- 蒙特卡洛模拟（Monte Carlo simulation）