This is the 25th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021.

describe

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

Example 1: input: nums1 = [1,2,2,1], nums2 = [2,2] output: [2,2] example 2: input: nums1 = [4,9,5], nums2 = [9,4,9,8,4] output: [4,9]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.

Problem.

I didn’t quite understand the first part of the instructions.

The order of the two arrays is not needed.

At first I thought that considering the order of two arrays, like [4,9] in example 2, would be more difficult, and that the only way to do it might be to iterate through a two-level loop.

Since we don’t need to worry about the order of the results, we can consider using a map to store the number of occurrences of each number, and then returning the least number of occurrences of the same number as the result.

public int[] intersect(int[] nums1, int[] nums2) {
    Map<Integer,Integer> map1=new HashMap<>();
    Map<Integer,Integer> map2=new HashMap<>();

    for (int i = 0; i < nums1.length; i++) {
        int num = nums1[i];
        Integer integer = map1.get(num);
        if (integer == null){
            integer = 1;
            map1.put(num,integer);
            continue;
        }
        integer +=1;
        map1.put(num,integer);
    }

    for (int i = 0; i < nums2.length; i++) {
        int num = nums2[i];
        Integer integer = map2.get(num);
        if (integer == null){
            integer = 1;
            map2.put(num,integer);
            continue;
        }
        integer +=1;
        map2.put(num,integer);
    }

    List<Integer> list = new ArrayList<>();
    Set<Integer> integers = map1.keySet();
    Iterator<Integer> iterator = integers.iterator();
    while (iterator.hasNext()){
        Integer next = iterator.next();
        Integer integer2 = map2.get(next);
        if (integer2==null) {continue; } Integer integer1 = map1.get(next); integer1=integer2>integer1? integer1:integer2;while (integer1-->0){ list.add(next); }}int[] result = new int[list.size()];
    for (int i = 0; i < list.size(); i++) {
        result[i]=list.get(i);
    }

    return result;
}
Copy the code

Run is run through.

But the efficiency is low and the code is long.

This part of the code should be optimized to combine it with the second loop to reduce the time complexity.

public int[] intersect1(int[] nums1, int[] nums2) { Map<Integer,Integer> map1=new HashMap<>(); List<Integer> list = new ArrayList<>(); for (int i = 0; i < nums1.length; i++) { int num = nums1[i]; Integer integer = map1.get(num); if (integer == null){ integer = 1; map1.put(num,integer); continue; } map1.put(num,++integer); } for (int i = 0; i < nums2.length; i++) { int num = nums2[i]; Integer integer1 = map1.get(num); If (integer1 == null){// If integer1 = null, no further operations are required. } if ( integer1! =0){ list.add(num); map1.put(num,--integer1); } } int[] result = new int[list.size()]; for (int i = 0; i < list.size(); i++) { result[i]=list.get(i); } return result; }Copy the code

Do not optimize do not know, an optimization to reduce more than 20 lines of code, but also map2 optimization dropped.

But why does this run result in a higher memory footprint?

That’s all for today.

Here is a programmer Xu Xiaobai, daily algorithm [is] my new open a column, primary record my daily learning algorithm, here also hope that I can stick to the daily learning algorithm, don’t know whether this article style you like, don’t mean you free praise, your thumb up, collection, and comments are after work I insist on more power.