面试题：C++ Lambda表达式在复杂STL场景下的应用及优化

Question

给定一个`std::vector<std::pair<int, std::string>>`，其中`pair`的第一个元素表示优先级，第二个元素表示字符串。要求使用Lambda表达式结合STL算法，按照优先级对向量进行排序。如果优先级相同，则按照字符串的字典序排序。并且，在排序后，需要找到优先级最高的所有字符串，并将它们拼接成一个新的字符串。请写出高效的代码实现，并说明如何优化代码的时间和空间复杂度。

Answer 1

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

std::string processVector(const std::vector<std::pair<int, std::string>>& vec) {
    // 排序
    std::vector<std::pair<int, std::string>> sortedVec = vec;
    std::sort(sortedVec.begin(), sortedVec.end(), [](const auto& a, const auto& b) {
        if (a.first != b.first) {
            return a.first > b.first;
        }
        return a.second < b.second;
    });

    // 找到优先级最高的所有字符串并拼接
    std::string result;
    if (!sortedVec.empty()) {
        int highestPriority = sortedVec[0].first;
        for (const auto& pair : sortedVec) {
            if (pair.first == highestPriority) {
                result += pair.second;
            }
        }
    }
    return result;
}

时间复杂度优化

1. 排序部分：std::sort 通常使用快速排序、归并排序或堆排序等高效排序算法，平均时间复杂度为 $O(n log n)$，这里 n 是向量的大小。在本代码中，使用了 std::sort 对向量进行排序，这已经是一个较为高效的做法。
2. 拼接部分：找到优先级最高的所有字符串并拼接的过程，遍历了一次排序后的向量，时间复杂度为 $O(n)$。整体算法的时间复杂度主要由排序部分决定，为 $O(n log n)$。

空间复杂度优化

1. 额外空间：代码中使用了一个 sortedVec 来存储排序后的结果，空间复杂度为 $O(n)$。如果希望进一步优化空间复杂度，可以选择对原向量 vec 进行就地排序（std::sort 可以做到），这样可以将空间复杂度降低到 $O(1)$（忽略递归调用栈等额外空间）。
2. 字符串拼接：在拼接字符串时，result 存储最终结果，空间复杂度为 $O(k)$，其中 k 是所有优先级最高的字符串长度之和。在最坏情况下，k 可能与 n 成正比，即所有字符串优先级都相同且都需要拼接，此时空间复杂度为 $O(n)$。

总体而言，通过就地排序可以将空间复杂度优化到 $O(1)$，而时间复杂度在当前实现下已经是较为高效的 $O(n log n)$。