找出数组中的第 K 大整数
题目¶
找出数组中的第K大整数
- 数组不是以整数的形式给出，而是字符串（前缀没有0）
- 数组的值可能会重复，而且要考虑重复，不能去重
数据结构与函数
解题：排序¶
class Solution {
public:
string kthLargestNumber(vector<string>& nums, int k) {
// 自定义比较函数，在 s1 对应的整数较大时返回 true，反之返回 false
auto cmp = [](const string& s1, const string& s2) -> bool{
// 首先比较字符串长度
if (s1.size() > s2.size()){
return true;
}
else if (s1.size() < s2.size()){
return false;
}
else{
// 长度相等时比较字符串字典序大小
return s1 > s2;
}
};
sort(nums.begin(), nums.end(), cmp);
return nums[k-1];
}
};
解题：堆排序¶
面试高频算法真题 | 阿秀的学习笔记 (interviewguide.cn)
#include<queue>
#include<vector>
//用大顶堆进行排序，再选第k大
class Solution {
public:
//第k大 => 大顶堆 => 大顶堆要升序 => 升序的话要传less函数
//less函数 => 要满足严格弱序 => 即<返回true; >=的情况返回false
struct LessCompare
{
//对比两个字符串的优先级
bool operator()(const string& lhs, const string& rhs)
{
auto lhs_size = lhs.size();
auto rhs_size = rhs.size();
if(lhs_size != rhs_size) {
//长的越大
return lhs_size < rhs_size;
} else { //相等，用字符串判断即可
return lhs < rhs;
}
}
};
string kthLargestNumber(vector<string>& nums, int k) {
//C++中的优先队列，其内部实现是大顶堆
std::priority_queue<string, std::vector<string>, LessCompare> queue;
//依次放入，优先队列是不去重的
for(const auto& item : nums) {
queue.emplace(item);
}
//若k==1，即第1大，就不要pop => 因此是先--
while(--k) {
queue.pop();
}
//取栈顶
return queue.top();
}
};
解题：快排¶
todo: 超时，还需要优化
//用快排，取第7大的元素即可
class Solution {
public:
//lhs <= rhs, return true
//否则，return false
bool lessAndEqual(const std::string& lhs, const std::string& rhs) {
auto lhs_size = lhs.size();
auto rhs_size = rhs.size();
if(lhs_size != rhs_size) {
//长的越大
return lhs_size < rhs_size;
} else { //相等，用字符串判断即可
return lhs <= rhs;
}
}
//对arr数组，[low, high]范围内进行快排
// 处理到下标为aim_idx的元素时，停止退出
void quickSort(vector<string>& arr, int low, int high, int aim_idx) {
auto key = arr[low]; //取最低位作为哨兵
auto i = low;
auto j = high;
while(i<j) {
//# j从右到左扫描
while(i<j && lessAndEqual(key, arr[j])==true ) {
//如果key<=arr[j], j继续往左走
--j;
}
if(i<j) {
//i<j即代表上面的while中途退出了，也就是发现了key>arr[j]
// 那么就要将arr[j]放到左侧
// 放完之后i要向右位移
arr[i++] = arr[j]; //如果发现key
}
//# i从左到右扫描
while(i<j && lessAndEqual(arr[i], key)==true ) {
//如果arr[i]<=key, i继续往右走
++i;
}
if(i<j) {
//i<j即代表上面的while中途退出了，也就是发现了arr[i]>key
// 那么要将arr[i]放到右侧
// 放完之后j要向左位移
arr[j--] = arr[i];
}
}
arr[i] = key; //key的正确位置是i
if(i == aim_idx) {
//已经找到目标位置
return; //结束
}
//没有到目标位置，需要继续排序
//看aim_idx在哪个位置
if(aim_idx < i)
{
//在左侧 => 对左侧排序即可
quickSort(arr, low, i-1, aim_idx);
}
else if(aim_idx > i)
{
//在右侧 => 对右侧排序即可
quickSort(arr, i+1, high, aim_idx);
}
}
string kthLargestNumber(vector<string>& nums, int k) {
auto size = nums.size();
//第k大元素所在的下标
int aim_idx = size - k;
//size k aim_idx 公式
//1 1 0 1-1
//5 2 3 5-2
//5 3 2 5-3
//5 1 4 5-1
quickSort(nums, 0, size-1, aim_idx);
return nums[aim_idx];
}
};