Java simple solution using only 1 hashset, O(n)


  • -2

    The idea is similar to most of the Java Hashset solutions, while only 1 Hashset is used.

    public class Solution {
        public int[] intersection(int[] nums1, int[] nums2) {
            Set<Integer> dict = new HashSet<Integer>();
            int count=0;
            for(int i=0;i<nums1.length;i++){
                dict.add(nums1[i]);
            }
            for(int i=0;i<nums2.length;i++){
                if(dict.contains(nums2[i])){
                    //handle duplicate
                    dict.remove(nums2[i]);
                    count++;
                }
            }
            int[] ret = new int[count];
            for(int i=0;i<nums1.length;i++){
                dict.add(nums1[i]);
            }
            for(int i=0;i<nums2.length;i++){
                if(dict.contains(nums2[i])){
                    //handle duplicate
                    dict.remove(nums2[i]);
                    ret[--count] = nums2[i];
                }
            }
            return ret;
        }
    }

  • 0

    Can anyone tell me why I'm receiving down vote? :(


  • 0
    U

    why you are trying to "handle duplicates" in a HashSet?, it's a set, all the elements are different


  • 0

    The "handle duplicates" is used for output, not HashSet. Since the return is an array, we need to check for the duplicates.


  • 0
    T

    Heh, yes, it's O(n+m), but you're doing the intersection twice (just to calculate the size of the result) which is a lot of extra boxing and even code duplication. You're doing 4 times more set lookups then necessary. You can either pre-allocate an array and trim unused values or just use an auto-growing List to collect results.

    Tip: notice that the result cannot be bigger than the smaller array's length: if it was longer then something would be included that's not part of the intersection.

    See one of my solutions for more.


Log in to reply
 

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