LeetCode - Easy - 349. Intersection of Two Arrays

傷城~ 2023-01-02 15:26 130阅读 0赞

## Topic ##

*  Hash Table
 *  Two Pointers
 *  Binary Search
 *  Sort

## Description ##

[https://leetcode.com/problems/intersection-of-two-arrays/][https_leetcode.com_problems_intersection-of-two-arrays]

Given two arrays, write a function to compute their intersection.

**Example 1**:

Input: nums1 = [1,2,2,1], nums2 = [2,2]
    Output: [2]

**Example 2**:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
    Output: [9,4]

**Note**:

*  Each element in the result must be unique.
 *  The result can be in any order.

## Analysis ##

方法一：我写的，使用Java8的特性

方法二：set的retainAll方法

方法三：传统做法

方法四：使用Java8的特性，比方法一更精简

方法五：位图法

还有其他方法，如，将实参的两数组分别排序，然后用双指针，或二分查找寻找出共同元素。

## Submission ##

import java.util.Arrays;
    import java.util.HashSet;
    import java.util.Set;
    import java.util.stream.Collectors;
    
    public class IntersectionOfTwoArrays { 
    
    	// 方法一：我写的，使用 java8的特性
    	public int[] intersection1(int[] nums1, int[] nums2) { 
    		Set<Integer> set1 = Arrays.stream(nums1).boxed().collect(Collectors.toSet());
    
    		Set<Integer> tmp = new HashSet<>();
    		for (int x : nums2)
    			if (set1.contains(x))
    				tmp.add(x);
    
    		return tmp.stream().mapToInt(Integer::intValue).toArray();
    	}
    
    	// 方法二：set的retainAll方法
    	public int[] intersection2(int[] nums1, int[] nums2) { 
    		Set<Integer> set1 = Arrays.stream(nums1).boxed().collect(Collectors.toSet());
    		Set<Integer> set2 = Arrays.stream(nums2).boxed().collect(Collectors.toSet());
    		set1.retainAll(set2);
    		return set1.stream().mapToInt(Integer::intValue).toArray();
    	}
    
    	// 方法三：传统做法
    	public int[] intersection3(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;
    	}
    
    	// 方法四：使用Java8的精简版
    	public int[] intersection4(int[] nums1, int[] nums2) { 
    		Set<Integer> set = Arrays.stream(nums2).boxed().collect(Collectors.toSet());
    		return Arrays.stream(nums1).distinct().filter(e -> set.contains(e)).toArray();
    	}
    
    	// 方法五：位图法
    	public int[] intersection5(int[] nums1, int[] nums2) { 
    		int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
    		int[] ans = new int[nums1.length];
    		int idx = 0;
    		for (int i : nums1) { 
    			if (i > max)
    				max = i;
    			if (i < min)
    				min = i;
    		}
    		for (int i : nums2) { 
    			if (i > max)
    				max = i;
    			if (i < min)
    				min = i;
    		}
    		boolean[] map = new boolean[max - min + 1];
    		for (int i : nums1)
    			map[i - min] = true;
    		for (int i : nums2) { 
    			if (map[i - min]) { 
    				ans[idx++] = i;
    				map[i - min] = false;
    			}
    		}
    		return Arrays.copyOf(ans, idx);
    	}
    
    }

## Test ##

import static org.junit.Assert.*;
    
    import java.util.Arrays;
    
    import org.junit.Test;
    
    public class IntersectionOfTwoArraysTest { 
    
    	@Test
    	public void test1() { 
    		IntersectionOfTwoArrays obj = new IntersectionOfTwoArrays();
    		assertArrayEquals(new int[] {  2 }, //
    				obj.intersection1(new int[] {  1, 2, 2, 1 }, new int[] {  2, 2 }));
    
    		int[] expected = {  9, 4 };
    		int[] actual = obj.intersection1(new int[] {  4, 9, 5 }, new int[] {  9, 4, 9, 8, 4 });
    		Arrays.sort(expected);
    		Arrays.sort(actual);
    		assertArrayEquals(expected, actual);
    	}
    
    	@Test
    	public void test2() { 
    		IntersectionOfTwoArrays obj = new IntersectionOfTwoArrays();
    		assertArrayEquals(new int[] {  2 }, // 
    				obj.intersection2(new int[] {  1, 2, 2, 1 }, new int[] {  2, 2 }));
    
    		int[] expected = {  9, 4 };
    		int[] actual = obj.intersection2(new int[] {  4, 9, 5 }, new int[] {  9, 4, 9, 8, 4 });
    		Arrays.sort(expected);
    		Arrays.sort(actual);
    		assertArrayEquals(expected, actual);
    	}
    
    	@Test
    	public void test3() { 
    		IntersectionOfTwoArrays obj = new IntersectionOfTwoArrays();
    		assertArrayEquals(new int[] {  2 }, //
    				obj.intersection3(new int[] {  1, 2, 2, 1 }, new int[] {  2, 2 }));
    
    		int[] expected = {  9, 4 };
    		int[] actual = obj.intersection3(new int[] {  4, 9, 5 }, new int[] {  9, 4, 9, 8, 4 });
    		Arrays.sort(expected);
    		Arrays.sort(actual);
    		assertArrayEquals(expected, actual);
    	}
    
    	@Test
    	public void test4() { 
    		IntersectionOfTwoArrays obj = new IntersectionOfTwoArrays();
    		assertArrayEquals(new int[] {  2 }, //
    				obj.intersection4(new int[] {  1, 2, 2, 1 }, new int[] {  2, 2 }));
    
    		int[] expected = {  9, 4 };
    		int[] actual = obj.intersection4(new int[] {  4, 9, 5 }, new int[] {  9, 4, 9, 8, 4 });
    		Arrays.sort(expected);
    		Arrays.sort(actual);
    		assertArrayEquals(expected, actual);
    	}
    
    	@Test
    	public void test5() { 
    		IntersectionOfTwoArrays obj = new IntersectionOfTwoArrays();
    		assertArrayEquals(new int[] {  2 }, //
    				obj.intersection5(new int[] {  1, 2, 2, 1 }, new int[] {  2, 2 }));
    
    		int[] expected = {  9, 4 };
    		int[] actual = obj.intersection5(new int[] {  4, 9, 5 }, new int[] {  9, 4, 9, 8, 4 });
    		Arrays.sort(expected);
    		Arrays.sort(actual);
    		assertArrayEquals(expected, actual);
    	}
    }

[https_leetcode.com_problems_intersection-of-two-arrays]: https://leetcode.com/problems/intersection-of-two-arrays/