一个乱序数组，求第 K 大的数。排序方式使用字典序

要求一个乱序数组中第 K 大的数，并且排序方式使用字典序，可以使用多种方法来实现。这里提供两种常见的方法：一种是直接排序后取第 K 大的数，另一种是使用快速选择算法。

方法一：直接排序 排序：将数组按字典序排序。 取第 K 大的数：从排序后的数组中取出第 K 大的数。 示例代码

▼
cpp
复制代码
#include <iostream>
#include <vector>
#include <algorithm>

std::string findKthLargestLexicographical(std::vector<std::string>& arr, int k) {
    // 按字典序排序
    std::sort(arr.begin(), arr.end());
    // 取第 K 大的数（注意索引是从 0 开始的）
    return arr[arr.size() - k];
}

int main() {
    std::vector<std::string> arr = {"banana", "apple", "cherry", "date"};
    int k = 2;
    std::string result = findKthLargestLexicographical(arr, k);
    std::cout << "第 " << k << " 大的数是: " << result << std::endl;
    return 0;
}

方法二：快速选择算法 快速选择算法是一种高效的查找第 K 大元素的算法，其平均时间复杂度为 O(n)。虽然标准库中的 nth_element 函数也可以实现类似的功能，但这里我们手动实现一个简单的快速选择算法。

示例代码

▼
cpp
复制代码
#include <iostream>
#include <vector>
#include <algorithm>

int partition(std::vector<std::string>& arr, int left, int right) {
    std::string pivot = arr[right];
    int i = left - 1;
    for (int j = left; j < right; ++j) {
        if (arr[j] <= pivot) {
            ++i;
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i + 1], arr[right]);
    return i + 1;
}

std::string quickSelect(std::vector<std::string>& arr, int left, int right, int k) {
    if (left == right) {
        return arr[left];
    }
    int pivotIndex = partition(arr, left, right);
    if (k == pivotIndex) {
        return arr[k];
    } else if (k < pivotIndex) {
        return quickSelect(arr, left, pivotIndex - 1, k);
    } else {
        return quickSelect(arr, pivotIndex + 1, right, k);
    }
}

std::string findKthLargestLexicographical(std::vector<std::string>& arr, int k) {
    int n = arr.size();
    return quickSelect(arr, 0, n - 1, n - k);
}

int main() {
    std::vector<std::string> arr = {"banana", "apple", "cherry", "date"};
    int k = 2;
    std::string result = findKthLargestLexicographical(arr, k);
    std::cout << "第 " << k << " 大的数是: " << result << std::endl;
    return 0;
}

总结 直接排序：简单易实现，适用于数据量较小的情况。 快速选择算法：效率更高，适用于数据量较大的情况。