LeetCode349 Intersection of Two Arrays
LeetCode349 Intersection of Two Arrays
用户1665735
发布于 2019-02-19 14:30:30
发布于 2019-02-19 14:30:30
原题
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. 即给两个数组，寻找在两个数组中都存在的数字，要求结果中的数字唯一，且没有顺序要求。
方法一
很容易就想到使用两次遍历找到重复的数字，这里使用HashSet来去重。
public int[] intersection(int[] nums1, int[] nums2) {
int[] record = new int[nums2.length];
Set<Integer> set = new HashSet<Integer>();
int count = 0,k=0;
for(int i = 0;i<nums1.length;i++){
for(int j =0;j<nums2.length;j++){
if(nums1[i]==nums2[j]&&record[j]==0&&count<nums2.length+1){
count++;
set.add(nums2[j]);
break;
}
}
}
int[] result = new int[set.size()];
for(Integer s:set){
result[k++] = s;
}
return result;
}但是很明显耗时较长，仅超过8%的提交者。
方法二
可以仅使用一次遍历找到重复的数字，但是要求数组是有序的。使用两个指针分别指向两个数组当前正在比较的数字。哪个较小就加一，相同则加入集合并且两个指针都加一。
public int[] intersection(int[] nums1, int[] nums2) {
int i=0,j=0,a=0;
Set<Integer> set = new HashSet<Integer>();
int length = nums1.length+nums2.length;
Arrays.sort(nums1);
Arrays.sort(nums2);
for(int k = 0;k<length;k++){
if(i>=nums1.length)
break;
else if(j>=nums2.length)
break;
else if(nums1[i]<nums2[j])
i++;
else if (nums1[i] > nums2[j])
j++;
else {
set.add(nums1[i]);
i++;
j++;
}
}
int[] result = new int[set.size()];
for(Integer s:set){
result[a++] = s;
}
return result;
}这次超过82%的提交者~
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017年02月14日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录