algorithm - 从另一个数组中替换一个数组的元素以最小化第一个数组的总和

Question

<分区>

Answer 1

您的算法将不起作用。最终输出数组中可能会保留相对较大的元素。我会在这里发布相关的测试用例。

就目前而言，我会告诉你什么会起作用。

解决方案#1

经过排序，这个问题只是归并排序的一个子问题。这与归并排序的归并步骤完全相同。

• 排序 A 和 B
• 合并A和B直到输出数组由n个元素组成

合并的伪代码如下所示:

function merge(int[] A, int[] B):
    n := length(A)
    m := length(B)
    int[] output := new int[n]
    i := 0
    j := 0
    k := 0
    while i < n and j < m and k < n do
        if A[i] <= B[j]
            output[k] := A[i]
            i := i + 1

        else if A[i] > B[j]
            output[k] := B[j]
            j := j + 1

        k := k + 1

    end


    while i < n and k < n do
        output[k] := A[i]
        i := i + 1
        k := k + 1
    end


    while j < m and k < n do
        output[k] := B[j]
        j := j + 1
        k := k + 1
    end

return output

排序 O(nlogn) 和合并的时间复杂度需要 O(n) 时间和 O(n) 空间。

解决方案 #2 [更快的方法]

• 排序数组 A 和 B
• 通过二进制搜索方法获取 n 最小的元素。这类似于finding median of two sorted array的方式.在这里，您将寻找 n 个最小元素，而不是寻找 median，并将此范围内的所有元素放入输出数组中。

排序的时间复杂度为 O(nlogn)，第二步的时间复杂度为 O(log(n + m))。