常用逻辑

目录

• 1、多个有序数组取topk
• 2、实现一个noncopyable类

对于多个有序数组取 top k 的问题，一个常见的思路是使用最小堆（min heap）来处理。

#include <iostream>
#include <vector>
#include <queue>

std::vector<int> findTopK(const std::vector<std::vector<int>>& arrays, int k) {
    struct ArrayElement {
        int value; // 元素的值
        int arrayIndex; // 所属数组的索引
        int elementIndex; // 元素在所属数组中的索引

        ArrayElement(int v, int ai, int ei) : value(v), arrayIndex(ai), elementIndex(ei) {}
    };

    auto compare = [](const ArrayElement& a, const ArrayElement& b) { return a.value > b.value; };
    std::priority_queue<ArrayElement, std::vector<ArrayElement>, decltype(compare)> minHeap(compare);

    // 初始化最小堆，将每个数组的第一个元素加入堆中
    for (int i = 0; i < arrays.size(); ++i) {
        if (!arrays[i].empty()) {
            minHeap.emplace(arrays[i][0], i, 0);
        }
    }

    std::vector<int> result;
    while (!minHeap.empty() && result.size() < k) {
        ArrayElement top = minHeap.top();
        minHeap.pop();

        result.push_back(top.value);

        // 将当前元素所属数组的下一个元素加入堆中
        if (top.elementIndex + 1 < arrays[top.arrayIndex].size()) {
            minHeap.emplace(arrays[top.arrayIndex][top.elementIndex + 1], top.arrayIndex, top.elementIndex + 1);
        }
    }

    return result;
}

int main() {
    std::vector<std::vector<int>> arrays = {{1, 4, 7}, {2, 5, 8}, {3, 6, 9}};
    int k = 5;

    std::vector<int> topK = findTopK(arrays, k);

    std::cout << "The top " << k << " elements are: ";
    for (int num : topK) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

在上述示例中，我们定义了一个 ArrayElement 结构体来表示每个数组的元素，包括元素的值、所属数组的索引和元素在所属数组中的索引。

findTopK 函数使用最小堆来处理取 top k 的逻辑。首先，我们将每个数组的第一个元素加入最小堆中。然后，从堆中依次取出最小的元素，并将其添加到结果集中。同时，我们还将当前元素所属数组的下一个元素加入最小堆中。重复这个过程，直到取出 k 个元素或者堆为空。

运行上述代码，将输出多个有序数组中的前 k 个最小元素。你可以根据自己的需求调整输入的数组和 k 值进行测试。

2、实现一个noncopyable类