Yifans_Z's Blog.

LeetCode Intersection of Two Arrays 349

字数统计: 244阅读时长: 2 min
2016/08/22 Share

349. 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.

自己的解法

使用 set 进行去重

public static int[] intersection2(int[] nums1, int[] nums2) {
Set<Integer> nums1Set = new HashSet<>();
Set<Integer> set = new HashSet<>();
for (int integer : nums1) {
nums1Set.add(integer);
}
for (int integer : nums2) {
if (nums1Set.contains(integer)) {
set.add(integer);
}
}
int[] result = new int[set.size()];
int i = 0;
for (int integer : set) {
result[i] = integer;
i++;
}
return result;
}

别人的思路

LeetCode – Intersection of Two Arrays (Java)

Binary Search

public int[] intersection(int[] nums1, int[] nums2) {
Arrays.sort(nums1);
Arrays.sort(nums2);
ArrayList<Integer> list = new ArrayList<Integer>();
for(int i=0; i<nums1.length; i++){
if(i==0 || (i>0 && nums1[i]!=nums1[i-1])){
if(Arrays.binarySearch(nums2, nums1[i])>-1){
list.add(nums1[i]);
}
}
}
int[] result = new int[list.size()];
int k=0;
for(int i: list){
result[k++] = i;
}
return result;
}

Time = O(nlog(n)).
Space = O(n).

CATALOG
  1. 1. 自己的解法
  2. 2. 别人的思路