Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Topic describes

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

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2] output: [2,2]Copy the code

Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]Copy the code

Description:

  • The number of occurrences of each element in the output should be the same as the minimum number of occurrences of the element in both arrays. We can ignore the order of the output.

Advanced:

  • What if the given array is already sorted? How will you optimize your algorithm?
  • If nums1 is much smaller than NUMs2, which method is better?
  • What do you do if nums2 elements are stored on disk, memory is limited, and you can’t load all elements into memory at once?

Answer key

1. Sort the two arrays first, then move the double pointer, if they are the same, insert the new array.

public int[] intersect(int[] nums1, int[] nums2) { // 1. Arrays.sort(nums1); Arrays.sort(nums2); int left = 0; int right = 0; int k = 0; int[] result = new int[nums1.length]; //2. Use double Pointers for comparison. If they are equal, place the element in the array and move the two Pointers backwards. While (left < nums1.length && right < nums2.length) {if (nums1[left] == nums2[right]) {result[k] = nums1[left]; left++; right++; k ++; }else if (nums1[left] < nums2[right]) { left++; }else { right++; } } return Arrays.copyOfRange(result,0,k); }Copy the code

  1. The map is storedAll the elements and occurrences of the first array are stored, and the second array iterates through the map.

Through the storage times, the number of common occurrences can be matched

public static int[] intersect(int[] nums1, int[] nums2) { Map<Integer, Integer> map = new HashMap<>(); int[] ints = new int[nums1.length]; Integer count = 0; int k = 0; For (int num: nums1) {count = map.get(num); if (null == count) { map.put(num,1); }else { map.put(num,count+1); For (int num: nums2) {count = map.get(num); if (null ! = count) { ints[k] = num; k ++; count --; If (0 == count) {map.remove(num); if (0 == count) {map.remove(num); }else { map.put(num,count); } } } return Arrays.copyOfRange(ints,0,k); }Copy the code