首页 > 代码库 > 349. Intersection of Two Arrays【双指针|二分】

349. Intersection of Two Arrays【双指针|二分】

2024-09-10 18:50:31   217人阅读

2017/3/23 15:41:47

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.
 
作弊版：Python
  1. classSolution(object):
  2. def intersection(self, nums1, nums2):
  3. return list(set( nums1 )& set(nums2))
 
版本1：Java  O(m*n)  循环检查  
  1. publicclassSolution{
  2. publicint[] intersection(int[] nums1,int[] nums2){
  3. Set<Integer> set =newHashSet<Integer>();
  4. for(int i=0;i<nums1.length;i++)
  5. for(int j=0;j<nums2.length;j++)
  6. if( nums1[i]== nums2[j]){
  7. set.add(nums1[i]);
  8. break;
  9. }
  10. Object[] obj = set.toArray();
  11. int[] rs =newint[obj.length];
  12. for(int i=0;i<obj.length;i++)
  13. rs[i]=(int)obj[i];
  14. return rs;
  15. }
  16. }
 
版本2：Java  O(m+n)  借助哈希表+Set，或者双Set
  1. publicint[] intersection(int[] nums1,int[] nums2){
  2. Map<Integer,Boolean> map =newHashtable<Integer,Boolean>();
  3. Set<Integer> set =newTreeSet<Integer>();
  4. for(int i=0;i<nums1.length;i++)
  5. map.put( nums1[i],true);
  6. for(int j=0;j<nums2.length;j++){
  7. if(map.get(nums2[j])==null)continue;
  8. set.add(nums2[j]);
  9. }
  10. int i =0;
  11. int[] rs =newint[set.size()];
  12. for(Integer num : set )
  13. rs[i++]= num;
  14. return rs;
  15. }
 
 

349. Intersection of Two Arrays【双指针|二分】


联系
我们