A, the title

Given two arrays, write a function to calculate their intersection

Second, the train of thought

Create a list array, iterate over NUMs1, count the elements that appear in it, iterate over NUMs2 if the element list contains, then output.

Initial code

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        ArrayList<Integer> list = new ArrayList<>();        
        for(int num : nums1){
            list[num]++;
        }
        int []list2=new int[(nums1.length<nums2.length?nums1.length:nums2.length)];
        for(int num : nums2){
            if(list[num]>0){ list2[i++]=num; list.remove(num); }}returnlist2; }}Copy the code

4. Bug analysis during debugging

bug 1

If num is too large, the space allocated by the list is too large. Add element to list add element to list: list.add

 list.add(num);
Copy the code

Then use list.contains(num) to check if the list contains num.

bug 2

It happens twice. Remove failed? No, remove one and then another. How do I remove duplicate elements?

if(list.contains(num)&&(list2.contains(num)==0))
Copy the code

This works, but an error is reported that list2 is an array and cannot use contains. I’ll change the type

bug 3

Cannot compare Boolean and int, Boolean should result in false or true instead

if(list.contains(num)&&(list2.contains(num)==false)) {Copy the code

bug 4

A List cannot be returned directly as an array

int [] list3=new int[list2.size()];
        for(int i=0; i<list3.length; i++){ list3[i]=list2.get(i); }return list3;
Copy the code

Get the elements in the list using the get () function

bug 5

But there was an error when submitting:

List. Remove (num) remove index=num To remove elements, use…… Remove () removes the element, but there is a conflict because the int is passed in. Remove has two definitions:

public E remove(int index); 
public boolean remove(Object o);
Copy the code

When \ is passed an int, it is automatically called as the above method. The method below to remove a particular element requires passing in an Object Object. So to avoid confusion, the Int passed in is wrapped

list.remove((Integer)num);
Copy the code

5. Final code results

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        ArrayList<Integer> list = new ArrayList<>();
        ArrayList<Integer> list2 = new ArrayList<>();
        for (int num : nums1){
            list.add(num);
        }
        // int []list2=new int[(nums1.length<nums2.length?nums1.length:nums2.length)];
        // int i = 0;
        for (int num : nums2){
            if (list.contains(num)&&(list2.contains(num)==false)){ // list2[i++]=num; list2.add(num); // list.remove(num); list.remove((Integer)num); / /}}return list2;
        int [] list3=new int[list2.size()];
        for(int i=0; i<list3.length; i++){ list3[i]=list2.get(i); }returnlist3; }}Copy the code

It took too long to run because I created two arrays and did two traversals.

Vi. Official answers

(1) Code

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set1 = new HashSet<Integer>();
        Set<Integer> set2 = new HashSet<Integer>();
        for (int num : nums1) {
            set1.add(num);
        }
        for (int num : nums2) {
            set2.add(num);
        }
        return getIntersection(set1, set2);
    }
    public int[] getIntersection(Set<Integer> set1, Set<Integer> set2) {
        if (set1.size() > set2.size()) {
            return getIntersection(set2, set1);
        }
        Set<Integer> intersectionSet = new HashSet<Integer>();
        for (int num : set1) {
            if (set2.contains(num)) {
                intersectionSet.add(num);
            }
        }
        int[] intersection = new int[intersectionSet.size()];
        int index = 0;
        for (int num : intersectionSet) {
            intersection[index++] = num;
        }
        returnintersection; }}Copy the code

(2) analysis

The official run, a very short time, analysis:

Create a set to place elements in an array, iterate through another array, and return the same elements. 1, use HashSet to avoid adding duplicate elements, O(1) 2, use a nice if condition to loop through small arrays, reduce time 3, can add a boundary condition

7. HashSet Theory

Data structure just a little bit of sorting, doing it as you go.

A HashSet takes objects as elements, has no order in which elements are put, and rejects duplicate elements (insert and delete are efficient, but retrieve is inefficient). In contrast to Arraylist, lists are ordered, repeatable, efficient to retrieve but inefficient to delete and insert. A HashMap takes a set of objects as elements (keys and their mapped values).

“A HashMap can be viewed as three views: a Set of keys, a Collection of values, and a Set of entries. Here a HashSet is a view of what is essentially a HashMap.” A HashSet contains a HashMap, which has different dimensions. Add elements with add

Eight, a HashMap:

A Hashmap is a combination of an array and a list (called a “list hash” in data structures)

When we put an element into a HashMap, we first hash the key to its position in the array (that is, the index), and then we can put the element into its position. If there are already other elements in the same place, the elements in the same place are stored in a linked list, with the new ones at the head and the first ones at the end.

Put () for storing and get () for reading and find out if there’s a key containsKey()

Write in the back

Sorting is full of satisfaction. What ideas do you have

HashSet theory