Golang concise 2 solutions using map and binary search


  • 0

    using map

    func intersect(nums1 []int, nums2 []int) []int {
    	m := make(map[int]int)
    	for _, n := range nums1 {
    		if count, ok := m[n]; !ok {
    			m[n] = 1
    		} else {
    			m[n] = count + 1
    		}
    	}
    
    	var res []int
    	for _, n := range nums2 {
    		if count, ok := m[n]; ok && count > 0 {
    			res = append(res, n)
    			m[n] = count - 1
    		}
    	}
    	return res
    }
    

    If arrays are sorted, we can use binary search method.
    Iterate through nums1, then find lower bound in nums2 that is equal or larger than nums1[i] and if lower bound value is equal to nums1[i], then we can add that to a result. Whenever we find one, we can discard the lower bound.

    func intersect(nums1 []int, nums2 []int) []int {
    	sort.Ints(nums1)
    	sort.Ints(nums2)
    
    	var res []int
    	for _, n := range nums1 {
    		if index := find(nums2, n); index >= 0 && index < len(nums2) && nums2[index] == n {
    			res = append(res, n)
    			nums2 = nums2[index+1:]
    		}
    	}
    	return res
    }
    
    func find(nums []int, n int) int {
    	left, right := 0, len(nums)-1
    	var mid int
    	for left < right {
    		mid = left + (right-left)/2
    		switch {
    		case nums[mid] >= n:
    			right = mid
    		case nums[mid] < n:
    			left = mid + 1
    		}
    	}
    	return right
    
    

Log in to reply
 

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