如何编写O(nlogn)复杂度的双无序数组目标和配对检测代码

实现思路 #

原单数组的二分查找思路可以直接迁移适配双数组场景：对其中一个数组排序后，遍历另一个数组的所有元素，在已排序数组中二分查找是否存在K - 当前遍历元素的目标值即可。假设两个数组长度分别为lenA和lenB，整体时间复杂度为O(min(lenA, lenB) * log(min(lenA, lenB)) + max(lenA, lenB) * log(min(lenA, lenB)))，同量级下整体为O(nlogn)，符合要求。

操作步骤 #

• 优先取两个数组中长度更短的数组进行升序排序，进一步降低排序的时间开销
• 遍历长度更长的数组中的每一个元素current
• 对每一个current，在已排序的短数组中二分查找目标值K - current
• 如果找到匹配的目标值，直接返回true
• 遍历完所有元素都没有找到匹配项，返回false

伪代码实现 #

int find_sumPair_twoArrays (A[], lenA, B[], lenB, K)
{
    // 优先排序短数组减少耗时，交换数组保证A是更短的数组
    if (lenA > lenB) {
        swap(A, B)
        swap(lenA, lenB)
    }
    // 排序较短的数组A
    Sort(A, lenA)
    // 遍历较长的数组B的每个元素
    for (i = 0 to lenB - 1) {
        target = K - B[i]
        // 在已排序的A数组中二分查找目标值，查找成功返回索引、失败返回-1
        findResult = binarySearch(A, 0, lenA - 1, target)
        if (findResult != -1) {
            // 找到匹配配对
            return 1
        }
    }
    // 遍历完无匹配
    return -1
}

补充说明 #

如果业务要求不能重复使用数组元素、或者有重复值校验需求，可以在二分查找匹配成功后加额外的校验逻辑，不影响整体时间复杂度。

内容的提问来源于stack exchange，提问作者segmentationfaultgonnakillme