需要帮助将“查找两个排序数组中的第 k 个最小的”转换为“第 k 个最大的”

Question

我有一些 C++ 代码，可以在 O(log(m * n)) 时间内找到两个排序数组的第 k 个最小项。我知道这不是最佳解决方案，并且我知道可以在 O(log(min(m, n))) 中解决它，但是我对此还不感兴趣。

我想转换这个函数以使其返回第 k 大的项目，但我很难让它工作。这肯定是一个需要仔细调整一些比较的问题，但我无法让它发挥作用。我可以在这里寻求帮助吗？

#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
#include <unordered_map>

using namespace std;

// speed: O(log( m * n) ))
// space: O(1)
int solveKthSmallest(vector<int>& A, vector<int>& B, int k, int aStart, int aEnd, int bStart, int bEnd)
{
    std::cout << "solveKthSmallest: (" << k << "): [" << aStart << "," << aEnd << "] [" << bStart << "," << bEnd << "]\n";

    // If the segment of on array is empty, it means we have passed all
    // its element, just return the corresponding element in the other array.
    if (aEnd < aStart) {
        return B[k - aStart];
    }
    if (bEnd < bStart) {
        return A[k - bStart];
    }

    // Get the middle indexes and middle values of A and B.
    int aIndex = (aStart + aEnd) / 2;
    int bIndex = (bStart + bEnd) / 2;
    int aValue = A[aIndex];
    int bValue = B[bIndex];

    // If 'k' is in the right half of A + B, remove the smaller left half.
    if (aIndex + bIndex < k) { 
        if (aValue > bValue) {
            return solveKthSmallest(A, B, k, aStart, aEnd, bIndex + 1, bEnd);
        } else {
            return solveKthSmallest(A, B, k, aIndex + 1, aEnd, bStart, bEnd);
        }
    } 
    // Otherwise, remove the larger right half.
    else { 
        if (aValue > bValue) {
            return solveKthSmallest(A, B, k, aStart, aIndex - 1, bStart, bEnd);
        } else {
            return solveKthSmallest(A, B, k, aStart, aEnd, bStart, bIndex - 1);       
        }
    }
    return -1;
}

double findKthSmallest(vector<int>& nums1, vector<int>& nums2, int kIdx) {
    return solveKthSmallest(nums1, nums2, kIdx, 0, nums1.size() - 1, 0, nums2.size() - 1);
}

void t1()
{
    vector nums1{ 1, 4, 5, 8, 9 }; 
    vector nums2{ 2, 3, 6, 7 };

/*
    A: [ 1, 4, 5, 8, 9  ] : An = 5
    B: [ 2, 3, 6, 7 ]     : Bn = 4

    Al        Am        Ar
      [ 1, 4, 5, 8, 9  ]         

    Bl     Bm       Br
      [ 2, 3, 6, 7 ]

    Al <= Am <= Bm <= (Ar & Br)
*/

    cout << findKthSmallest(nums1, nums2, 3) << "\n";
}

int main()
{
    t1();

    return 0;
}

我知道可以解决它并这样称呼它：

double findKthLargest(vector<int>& nums1, vector<int>& nums2, int kIdx) {
    int revIdx = nums1.size() + nums2.size() - 1 - kIdx;
    cout << "revIdx: " << revIdx << "\n";

    return solveKthSmallest(nums1, nums2, revIdx, 0, nums1.size() - 1, 0, nums2.size() - 1);
}

但是我想要的是修改solveKthSmallest方法（复制它并重命名solveKthLargest），以便它可以保留其原始算法，但像这样调用

return solveKthLargest(nums1, nums2, kIdx, 0, nums1.size() - 1, 0, nums2.size() - 1);

Answer 1

您所说的“解决方法”是最明智的方法。原因是

k

现在是反向位置，您仍然需要将其转换为索引。为此，您需要涉及两个数组的大小。由于

solveKthGreatest

将是一个递归函数，因此您需要在 each 递归调用上进行该转换。它看起来像这样：

int solveKthGreatest(vector<int>& A, vector<int>& B, int kIdx, int aStart, int aEnd, int bStart, int bEnd)
// Use of different parameter name                   ^^^^^^^^
{
    std::cout << "solveKthGreatest: (" << kIdx << "): [" << aStart << "," << aEnd << "] [" << bStart << "," << bEnd << "]\n";
    // Calculate the index from the reversed index we got as argument
    int k = A.size() + B.size() - 1 - kIdx;
    if (aEnd < aStart) {
        return B[k - aStart];
    }
    if (bEnd < bStart) {
        return A[k - bStart];
    }

    int aIndex = (aStart + aEnd) / 2;
    int bIndex = (bStart + bEnd) / 2;
    int aValue = A[aIndex];
    int bValue = B[bIndex];

    if (aIndex + bIndex < k) { 
        if (aValue > bValue) {
            return solveKthGreatest(A, B, kIdx, aStart, aEnd, bIndex + 1, bEnd);
//                                        ^^^^
        } else {
            return solveKthGreatest(A, B, kIdx, aIndex + 1, aEnd, bStart, bEnd);
        }
    } 
    else { 
        if (aValue > bValue) {
            return solveKthGreatest(A, B, kIdx, aStart, aIndex - 1, bStart, bEnd);
        } else {
            return solveKthGreatest(A, B, kIdx, aStart, aEnd, bStart, bIndex - 1);       
        }
    }
    return -1;
}

唯一的变化是：

• 参数名称从

  k

  更改为

  kIdx

• 局部变量的定义

  k

• 递归调用传递

  kIdx

  作为参数而不是

  k

您可以将

k

的计算移至使用

k

的表达式（共有三个），从而省略变量

k

，但这看起来更不优雅。

除非您有其他限制，否则我仍然会坚持您自己提出的解决方案。