[1985] Comments on The Choice of Sorting

[charmhe]

Based on the LCP string comparison algorithm you provided, it should be more clear to use a selection algorithm instead of the sorting on the whole array.

string kthLargestNumber(vector<string>& nums, int k) {
    nth_element(nums.begin(), nums.begin() + k - 1, nums.end(), [](auto& a, auto& b) {
        // return true if a is lexicographical larger than b.
        int N = a.size(), M = b.size();
        if (N > M) return true;
        if (N < M) return false;
        for (int i = 0; i < N; ++i) {
            if (a[i] != b[i])
                return a[i] > b[i];
        }
        return false;
    });
    return nums[k-1];    
}