This is the 13th day of my participation in Gwen Challenge

350. Intersection of two arrays II

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]

Example 2:

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

Output: [4, 9]

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.

link

Leetcode-cn.com/problems/in…

Thinking analytical

If both arrays are ordered at the same time, just set two Pointers to scan each array from the beginning.

  • If the corresponding two elements have the same value, the value is saved.
  • If two elements have different values, the index of the larger array stays the same and the pointer of the smaller array moves forward one bit. Why does the group with the small value move the pointer? Because the array is orderly arranged, only when the small value moves forward can it approach the large value of the other side step by step, and only then can it encounter the intersection value, which is not difficult to understand.
  • As soon as one set scans the entire array, the loop is terminated and the stored values are converted to array output.

Algorithm implementation

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int length1=nums1.length;
        int length2=nums2.length;
        int i=0,j=0;
        ArrayList<Integer> list=new ArrayList<>();
        while(i<length1&&j<length2){
            if(nums1[i]<nums2[j]){
                i++;
            }else if(nums1[i]==nums2[j]){
                list.add(nums1[i]);
                i++;
                j++;
            }else{ j++; }}int[] result = new int[list.size()];
        for(int a=0; a<list.size(); a++){ result[a]=list.get(a); }returnresult; }}Copy the code

The results

Advanced design

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?

This solution already satisfies the first and second requirements.

The third solution can be considered using a HashMap.