Swift 3 three solutions


  • 1
    Y
    class Solution {
        // hashset method, O(n) time and O(n) space
        func intersection(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
            var set = Set<Int>()
            var result = [Int]()
            for num in nums1 {
                set.insert(num)
            }
            for num in nums2 {
                if set.contains(num) {
                    result.append(num)
                    set.remove(num)
                }
            }
            return result
        }
        
        
        
        // binary search O(nlogn) time and use Hashset O(n)
        func intersection2(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
            if nums1.isEmpty || nums2.isEmpty {
                return [Int]()
            }
            let arr1 = nums1.sorted()
            var ans = Set<Int>()
            for num in nums2 {
                if search(arr1, num, 0, arr1.count - 1) {
                    ans.insert(num)
                }
            }
            return Array(ans)
        }
        
        func search(_ nums1: [Int], _ t: Int, _ left: Int, _ right: Int) -> Bool {
            var l = left, r = right
            while l < r {
                let mid = (l + r) / 2
                if nums1[mid] == t {
                    return true
                } else if nums1[mid] < t {
                    l = mid + 1
                } else {
                    r = mid
                }
            }
            return nums1[l] == t
        }
        
        
        
        
        
        // sorted and two pointers method, O(nlogn) time and O(1)space
        func intersection1(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
            let arr1 = nums1.sorted()
            let arr2 = nums2.sorted()
            var ans = [Int]()
            var p1 = 0, p2 = 0
            while p1 < arr1.count && p2 < arr2.count {
                while p1 + 1 < arr1.count && arr1[p1] == arr1[p1 + 1] {
                    p1 += 1
                }
                while p2 + 1 < arr2.count && arr2[p2] == arr2[p2 + 1] {
                    p2 += 1
                }
                if arr1[p1] == arr2[p2] {
                    ans.append(arr1[p1])
                    p1 += 1
                    p2 += 1
                } else if arr1[p1] < arr2[p2] {
                    p1 += 1
                } else {
                    p2 += 1
                }
            }
            return ans
        }
    }
    
    
    

Log in to reply
 

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