Leetcode-[Combination]-Intersection of Arrays/Linked Lists

这篇是综合几道关于Intersection of Arrays/Linked List 的Leetcode题，分析一下问题及其变体，并给出几种解法。

LeetCode 349. Intersection of Two Arrays

Question:

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

Example: Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].

Note:

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

Explanation:

题意是找到两个Array之间交叉的值，无重复。

Solution 1:
- Time Complexity: O( N^2 )
- Iterate two arrays, add intersection elements to a HashSet. Using set here to avoid repetition.

Solution 2: (My Choice)
- Time Complexity: O(N)
- Using two hashsets. The first hashset is to store all unduplicated elements in array1. Then add intersection between hashset1 and array2 to hashset2. It use more space but less time than solution 1.

Solution 3:
- Time Complexity: O(NlogN)
- Using two pointers. Sort two arrays first.

Code:

Solution1

public int[] intersection(int[] nums1, int[] nums2) {
    Set<Integer> set = new HashSet<>();
    for (int i = 0; i < nums1.length; i++) {
        for (int j = 0; j<nums2.length; j++) {
            if (nums1[i] == nums2[j]) {
                set.add(nums1[i]);
            }
        }
    }
    int[] ints = new int[set.size()];
    int i = 0;
    for (Integer num : set){
        ints[i++] = num;
    }
    return ints;
}

Solution2:

public int[] intersection(int[] nums1, int[] nums2) {
    Set<Integer> set = new HashSet<>();
    Set<Integer> intersection = new HashSet<>();
    for (int i = 0; i < nums1.length; i++) {
        set.add(nums1[i]);
    }
    for (int j = 0; j < nums2.length; j++) {
        if (set.contains(nums2[j])) {
            intersection.add(nums2[j]);
        }
    }
    int[] ints = new int[intersection.size()];
    int i = 0;
    for (Integer num : intersection){
        ints[i++] = num;
    }
    return ints;
}

Solution3: (Cite top solutions in Leetcode)

public class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set = new HashSet<>();
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int i = 0;
        int j = 0;
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] < nums2[j]) {
                i++;
            } else if (nums1[i] > nums2[j]) {
                j++;
            } else {
                set.add(nums1[i]);
                i++;
                j++;
            }
        }
        int[] result = new int[set.size()];
        int k = 0;
        for (Integer num : set) {
            result[k++] = num;
        }
        return result;
    }
}

LeetCode 350. Intersection of Two Arrays II

Question:

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

Example:

Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2].

Note:

Each element in the result should appear as many times as it shows in both arrays.
The result can be in any order.

Follow up:

What if the given array is already sorted? How would you optimize your algorithm?
What if nums1's size is small compared to nums2's size? Which algorithm is better?
What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

Explanation:

Here we need to solve the 3 follow up questions emphatically.

Solution1: Sort & Pointers
- Time Complexity: O(nlogn)
- Space Complexity: O(m + n)
- Sort two arrays first. Then use two pointers as the question 349.
Solution2: HashMap
- Time Complexity: O(N)
- Space Complexity: O(N)
- Use one hashmap to store array1 elements and counters. Find intersection by iterate elements in array2.
Importent Follow Up:

What if the given array is already sorted? How would you optimize your algorithm?

If it is sorted, we just need to use two pointers.

What if nums1's size is small compared to nums2's size? Which algorithm is better?

The hashmap solution is better.

What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once? (cite from top solution in Leetocode)

If only nums2 cannot fit in memory, put all elements of nums1 into a HashMap, read chunks of array that fit into the memory, and record the intersections.

If both nums1 and nums2 are so huge that neither fit into the memory, sort them individually (external sort), then read 2 elements from each array at a time in memory, record intersections.

Code:

Solution1:

public int[] intersect(int[] nums1, int[] nums2) {
    Arrays.sort(nums1);
    Arrays.sort(nums2);
    int i = 0;
    int j = 0;
    // 在这里选择了与349不一样的解法是，先定义好array，之后再截取返回。而不是先用ArrayList. 速度更快了。
    int[] result = new int[nums1.length < nums2.length ? nums1.length : nums2.length];
    int count = 0;
    while (i < nums1.length && j< nums2.length) {
        if (nums1[i] < nums2[j]) {
            i++;
        } else if (nums1[i] == nums2[j]) {
            result[count++] = nums1[i];
            i++;
            j++;
        } else {
            j++;
        }
    }
    return Arrays.copyOf(result, count);
}

Solution2:

public int[] intersect(int[] nums1, int[] nums2) {
    HashMap<Integer, Integer> map = new HashMap<>();
    int[] result = new int[nums1.length < nums2.length ? nums1.length : nums2.length];
    int count = 0;
    for (Integer n : nums1) {
        if(map.containsKey(n)) {
            map.put(n, map.get(n)+1);
        } else {
            map.put(n, 1);
        }
    }
    for (Integer m : nums2) {
        if(map.containsKey(m) && map.get(m) > 0) {
            result[count++] = m;
            map.put(m, map.get(m)-1);
        }
    }
    return Arrays.copyOf(result, count);
}

LeetCode 160. Intersection of Two Linked Lists

Question:

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

  A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗
  B:     b1 → b2 → b3

begin to intersect at node c1.

Notes:

If the two linked lists have no intersection at all, return null.
The linked lists must retain their original structure after the function returns.
You may assume there are no cycles anywhere in the entire linked structure.
Your code should preferably run in O(n) time and use only O(1) memory.

Explanation:

In order to use only O(1) memory and O(n) time, we can start from the same node (the head of shorter array) and get the intersection.

Code:

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if(headA == null || headB == null) {
        return null;
    }
    int lengthA = length(headA);
    int lengthB = length(headB);
    while (lengthA > lengthB) {
        headA = headA.next;
        lengthA --;
    }
    while(lengthB > lengthA) {
        headB = headB.next;
        lengthB --;
    }
    ListNode intersection = null;
    while(headA != headB ) {
        headA = headA.next;
        headB = headB.next;
    }
    intersection = headA;
    return intersection;
}
public int length(ListNode head) {
    int result= 0;
    while(head != null) {
        result ++;
        head = head.next;
    }
    return result;
}