乐趣区

关于hash:分享一个简单但挺有意思的算法题哈希二分双指针

1. 题目形容

给你两个有序 (递增) 整数数组 nums1 和 nums2,请你以数组模式返回两数组的交加,M为较长数组长度,N为较短数组长度。例如:
给定:nums1 = [1,2,3,4,5,6], nums2 = [1,2,3]
输入:[1,2,3]
这道题常见且并不难,有意思的是解法十分多,在 nums1 和 nums2 长短不同场景下,筛选最高效的解法

2. 哈希表

这是最容易想到的解法,对较短的数组进行哈希,遍历较长的数组,就能够失去交加

function intersect(nums1, nums2){let hash = new Set()// 这里用 set 来代表哈希,他们实质是一样的
    for (let i = 0; i < nums2.length; i++) {hash.add(nums2[i])
    }
    for (let i = 0; i < nums1.length; i++) {if (hash.has(nums1[i])) {ans.push(nums1[i])
        }
    }
    return ans
}

工夫复杂度:O(M+N)<br/>
空间复杂度: 对于较短的数组进行了哈希,O(N)

3. 二分查找

思考一个场景, 较长的数组十分长,哈希表的解法是线性的,显然没有很好的利用数组有序这个条件,这时二分查找怀才不遇,因为两者长度相差越大,二分效率越高;

function intersect(nums1, nums2){
    // 因为是递增,定义一个 left, 略微缩小下查找范畴
    let left = 0;
    for (let i = 0; i < nums2.length; i++) {
                
        // 二分查找
        let index = binarySearch(nums1, nums2[i], left)
        if (index != -1) {ans.push(nums2[i])
            left = index + 1
        }
    }    
    return ans
}

function binarySearch(nums, target, left  = 0, right = nums.length - 1){
        // 非凡解决 端点的状况 能够减速间断数组的查找
        if(nums[left] == target){return left}
        if(nums[right] == target){return right}
    while(left <= right){mid =  Math.floor((left + right)/2)
        if (nums[mid] == target) {return mid}else if(nums[mid] > target){right = mid - 1}else{left = mid + 1}
    }
    return -1
}

这里重点提一下为什么要优化二分查找的左终点,如果咱们不给定左终点,那么每次二分都是从 0len -1 二分,而因为数组是有序的,如果曾经在 num1 中找到了 target, 那么下一个待查找target 的地位必然在上一个 target 的左边,这样就防止了二分查找每次从 0 开始, 最现实状况下比方 nums1 = [1,2,3,4,5,6], nums2 = [4,5,6], 第一次查找到4, 残余的5,6 显然在 4 的左边,理论只有 O(N) 次就能够了
工夫复杂度:M为较长数组长度,N为较短数组长度,最差 / 均匀复杂度 O(N*logM),而且因为咱们优化了二分查找的左终点,最最现实状况下复杂度能够达到O(N);不是现实状况下,工夫复杂度取决于交加在nums1 中的散布状况,交加在 nums1 中越靠右散布,查找效率越高 <br/>
空间复杂度: 如果递归数组是援用的话,咱们只应用了常量级变量空间 O(1)

4. 双指针

如果两个数组长度相差不大,那么双指针显然效率更高;

function intersect(nums1, nums2){
    let m = n = 0
    while(m < nums1.length && n < nums2.length) {if (nums1[m] == nums2[n]) {ans.push(nums1[m])
            m++
            n++
        }else if (nums1[m] > nums2[n]) {n++}else{m++}
    }
    return ans
}

工夫复杂度:M为较长数组长度,N为较短数组长度,最好状况是 O(N),最坏状况是O(M)<br/>
空间复杂度: 只应用了常量级变量空间 O(1)

退出移动版