Three Java Solutions


  • 121
    D

    Use two hash sets

    Time complexity: O(n)

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

    Sort both arrays, use two pointers

    Time complexity: O(nlogn)

    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;
        }
    }
    

    Binary search

    Time complexity: O(nlogn)

    public class Solution {
        public int[] intersection(int[] nums1, int[] nums2) {
            Set<Integer> set = new HashSet<>();
            Arrays.sort(nums2);
            for (Integer num : nums1) {
                if (binarySearch(nums2, num)) {
                    set.add(num);
                }
            }
            int i = 0;
            int[] result = new int[set.size()];
            for (Integer num : set) {
                result[i++] = num;
            }
            return result;
        }
        
        public boolean binarySearch(int[] nums, int target) {
            int low = 0;
            int high = nums.length - 1;
            while (low <= high) {
                int mid = low + (high - low) / 2;
                if (nums[mid] == target) {
                    return true;
                }
                if (nums[mid] > target) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            }
            return false;
        }
    }

  • 27
    E

    Two-line java 8 solution using Stream

    Set<Integer> set = Arrays.stream(nums2).boxed().collect(Collectors.toSet());
    return Arrays.stream(nums1).distinct().filter(e-> set.contains(e)).toArray();

  • 1
    Z

    Why does the 2nd solution have O(nlogn) time complexity?


  • 6
    M

    Arrays.sort() will cost O(n log n) time


  • 0
    S

    haha nice. Do you use Arrays.stream, boxed, in the production? I feel like I need to get myself familiar with those as well.


  • 2
    D

    Hard.to read


  • 1
    V

    this is beautiful. please take away my kidney


  • 0
    V

    instead of "e-> set.contains(e)", use set::contains.


  • 2
    Z

    but the while loop would take n at worst I believe


  • 0

    @ericxliu can you explain this I am not getting it


  • 0

    said in Three Java Solutions:

    :

    what is the meaning of : when you write it in for loop


  • 0
    C

    @Harrywithcode : means iterating


  • 0
    J

    @ericxliu Special praise


  • 0

    @ericxliu Same idea, 3 lines in Swift:

    let nums1 = Array(Set(nums1)).sort()
    let nums2 = Set(nums2)
    return nums1.filter{ num in nums2.contains(num) }
    

  • 2
    O

    But I think the first solution's complexity is not O(n) because the function "contains()" complexity may be the O(nlgn) .So I think it is O(n^2lgn).Do you think about it? I am a fresh man,sorry to bother you .


  • 1
    Z

    @oubindo the search algorithm of HashSet is based on Hash Table Lookup which is O(1)


  • 1
    A

    @oubindo contains takes O(1) time because of the hash functions. http://stackoverflow.com/questions/25247854/hashset-contains-performance


  • 0
    C

    @zizizi Because sorting is O(nlogn)


  • 0
    W

    For the second solution, there is no need to use Set. When nums1[i] == nums2[j], we only incorporate nums1[i] into the result if nums1[i] is not equal to the end of the result, which is sorted. Here is a C++ version of the code:

    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        vector<int> res;
        res.reserve(min(nums1.size(), nums2.size()));
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());
        int i = 0, j = 0;
        while(i < nums1.size() && j < nums2.size()) {
            if(nums1[i] == nums2[j]) {
                if(res.empty() || res.back() != nums1[i])
                    res.push_back(nums1[i]);
                i++;
                j++;
            }
            else if(nums1[i] < nums2[j]){
                i++;
            }
            else {
                j++;
            }
        }
        res.shrink_to_fit();
        return res;
    }

  • 0
    W

    @zizizi Arrays.sort runs in O(nlogn) which is more than the O(n) to compare them so the time complexity defaults to O(nlogn).


Log in to reply
 

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