Java 6ms O(n+m) Solution with two Hashset


  • 5
    R

    The problem asks us to find the same integers in both arrays and return a non-duplicate result array.

    public int[] intersection(int[] nums1, int[] nums2) {
    		if (nums1.length == 0 || nums2.length == 0)
    			return new int[0];
    		Set<Integer> set = new HashSet<>();
    		Set<Integer> result = new HashSet<>();
    		for (int i = 0; i < nums2.length; i++) {
    			set.add(nums2[i]);
    		}
    		for (int i = 0; i < nums1.length; i++) {
    			if (set.contains(nums1[i])) {
    				result.add(nums1[i]);
    			}
    		}
    		int[] intersection = new int[result.size()];
    		int j = 0;
    		Iterator<Integer> it = result.iterator();
    		while(it.hasNext()) {
    			intersection[j] = it.next();
    			j++;
    		}
    		return intersection;	
    	}

  • 0
    S

    Good solution (better than the sorting approach IMO), but you should be careful iterating over a HashSet.

    "Iterating over this set requires time proportional to the sum of the
    HashSet instance's size (the number of elements) plus the "capacity"
    of the backing HashMap instance (the number of buckets). Thus, it's
    very important not to set the initial capacity too high (or the load
    factor too low) if iteration performance is important." (from the Javadocs)

    You can do something similar while keeping the O(n+m) complexity by using a LinkedList for intersection storage and using HashSet remove (which is O(1)) to avoid duplicates.

    e.g.

    LinkedList<Integer> result = new LinkedList<Integer>();
    for (int num : nums1) {
        if (set.contains(num)) {
            result.add(num);
            set.remove(num);
    }
    

    Cheers.


  • 0
    T

    You can go even farther and halve the set lookups:

    LinkedList<Integer> result = new LinkedList<Integer>();
    for (int num : nums1) {
        if (set.remove(num)) {
            result.add(num);
        }
    }

  • 0
    S

    Right. Good catch.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.