首页 > 代码库 > LeetCode Intersection of Two Arrays
LeetCode Intersection of Two Arrays
原题链接在这里: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.
题解:
用一个HashSet 来保存nums1的每个element.
再iterate nums2, 若HashSet contains nums2[i], 把nums2[i]加到res中,并把nums[i]从HashSet中remove掉.
Time Complexity: O(nums1.length + nums2.length). Space: O(nums1.length).
AC Java:
1 public class Solution { 2 public int[] intersection(int[] nums1, int[] nums2) { 3 HashSet<Integer> nums1Hs = new HashSet<Integer>(); 4 for(int num : nums1){ 5 nums1Hs.add(num); 6 } 7 8 List<Integer> res = new ArrayList<Integer>(); 9 for(int num : nums2){ 10 if(nums1Hs.contains(num)){ 11 res.add(num); 12 nums1Hs.remove(num); 13 } 14 } 15 int [] resArr = new int[res.size()]; 16 int i = 0; 17 for(int num : res){ 18 resArr[i++] = num; 19 } 20 return resArr; 21 } 22 }
也可以使用两个HashSet.
Time Complexity: O(nums1.length + nums2.length). Space: O(nums1.length).
AC Java:
1 public class Solution { 2 public int[] intersection(int[] nums1, int[] nums2) { 3 HashSet<Integer> nums1Hs = new HashSet<Integer>(); 4 HashSet<Integer> intersectHs = new HashSet<Integer>(); 5 for(int num : nums1){ 6 nums1Hs.add(num); 7 } 8 for(int num : nums2){ 9 if(nums1Hs.contains(num)){ 10 intersectHs.add(num); 11 } 12 } 13 14 int [] res = new int[intersectHs.size()]; 15 int i = 0; 16 for(int num : intersectHs){ 17 res[i++] = num; 18 } 19 return res; 20 } 21 }
Sort nums1 and nums2, 再用双指针 从头iterate两个sorted array.
Time Complexity: O(nlogn). Space: O(1).
AC Java:
1 public class Solution { 2 public int[] intersection(int[] nums1, int[] nums2) { 3 Arrays.sort(nums1); 4 Arrays.sort(nums2); 5 HashSet<Integer> hs = new HashSet<Integer>(); 6 int i = 0; 7 int j = 0; 8 while(i<nums1.length && j<nums2.length){ 9 if(nums1[i] < nums2[j]){ 10 i++; 11 }else if(nums1[i] > nums2[j]){ 12 j++; 13 }else{ 14 hs.add(nums1[i]); 15 i++; 16 j++; 17 } 18 } 19 20 int [] resArr = new int[hs.size()]; 21 int k = 0; 22 for(int num : hs){ 23 resArr[k++] = num; 24 } 25 return resArr; 26 } 27 }
LeetCode Intersection of Two Arrays
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。