关键词:
文章目录
LeetCode刷题笔记-数据结构-day20
215. 数组中的第K个最大元素
1.题目
原题链接:215. 数组中的第K个最大元素
2.解题思路
直接套快排模板:
void quick_sort(int q[], int l, int r)
if (l >= r) return;
int i = l - 1, j = r + 1, x = q[l + r >> 1];
while (i < j)
do i ++ ; while (q[i] < x);
do j -- ; while (q[j] > x);
if (i < j) swap(q[i], q[j]);
quick_sort(q, l, j), quick_sort(q, j + 1, r);
3.代码
class Solution
public:
int quickSort(vector<int>& nums,int l,int r,int k)
if(l>=r) return nums[k];
int x=nums[l+r>>1],i=l-1,j=r+1;
while(i<j)
do i++; while(nums[i]>x);
do j--; while(nums[j]<x);
if(i<j) swap(nums[i],nums[j]);
if(k<=j) return quickSort(nums,l,j,k);
else return quickSort(nums,j+1,r,k);
int findKthLargest(vector<int>& nums, int k)
return quickSort(nums,0,nums.size()-1,k-1);
;
347. 前 K 个高频元素
1.题目描述
原题链接:347. 前 K 个高频元素
2.解题思路
算法:哈希表+计数排序
具体实现:
- 首先使用哈希表统计所有数出现的次数
- 用计数排序,统计出出现次数最多的前k个元素的下界
- 最后遍历哈希表,将出现次数大于下界的数加入答案
3.代码
class Solution
public:
vector<int> topKFrequent(vector<int>& nums, int k)
int n=nums.size();
map<int,int> hash;
for(auto x:nums) hash[x]++;
vector<int> s(n+1);
for(auto [a,b]:hash) s[b]++;
int i=n,t=0;
while(t<k) t+=s[i--];
vector<int> res;
for(auto [a,b]:hash)
if(b>i) res.push_back(a);
return res;
;
leetcode刷题笔记-数据结构-day19(代码片段)
文章目录LeetCode刷题笔记-数据结构-day19997.找到小镇的法官1.题目描述2.解题思路3.代码1557.可以到达所有点的最少点数目1.题目描述2.解题思路3.代码841.钥匙和房间1.题目描述2.解题思路3.代码LeetCode刷题笔记-数据结构-day19997.找到小... 查看详情
leetcode刷题笔记-数据结构-day19(代码片段)
文章目录LeetCode刷题笔记-数据结构-day19997.找到小镇的法官1.题目描述2.解题思路3.代码1557.可以到达所有点的最少点数目1.题目描述2.解题思路3.代码841.钥匙和房间1.题目描述2.解题思路3.代码LeetCode刷题笔记-数据结构-day19997.找到小... 查看详情
leetcode刷题笔记-数据结构-day14(代码片段)
文章目录LeetCode刷题笔记-数据结构-day14155.最小栈1.题目描述2.解题思路3.代码1249.移除无效的括号1.题目描述2.解题思路3.代码1823.找出游戏的获胜者1.题目描述2.解题思路3.代码LeetCode刷题笔记-数据结构-day14155.最小栈1.题目描述原题... 查看详情
leetcode刷题笔记-数据结构-day21(代码片段)
文章目录LeetCode刷题笔记-数据结构-day21451.根据字符出现频率排序1.题目2.解题思路3.代码973.最接近原点的K个点1.题目2.解题思路3.代码LeetCode刷题笔记-数据结构-day21451.根据字符出现频率排序1.题目原题链接:451.根据字符出现频... 查看详情
leetcode刷题笔记-数据结构-day21(代码片段)
文章目录LeetCode刷题笔记-数据结构-day21451.根据字符出现频率排序1.题目2.解题思路3.代码973.最接近原点的K个点1.题目2.解题思路3.代码LeetCode刷题笔记-数据结构-day21451.根据字符出现频率排序1.题目原题链接:451.根据字符出现频... 查看详情
leetcode刷题笔记-数据结构-day12(代码片段)
文章目录LeetCode刷题笔记-数据结构-day1224.两两交换链表中的节点1.题目描述2.解题思路3.代码707.设计链表1.题目描述2.解题思路3.代码LeetCode刷题笔记-数据结构-day1224.两两交换链表中的节点1.题目描述原题链接:24.两两交换链表... 查看详情
leetcode刷题笔记-数据结构-day16(代码片段)
文章目录LeetCode刷题笔记-数据结构-day16199.二叉树的右视图1.题目描述2.解题思路3.代码113.路径总和II1.题目描述2.解题思路3.代码450.删除二叉搜索树中的节点1.题目描述2.解题思路3.代码LeetCode刷题笔记-数据结构-day16199.二叉树的右视... 查看详情
leetcode刷题笔记-数据结构-day15(代码片段)
文章目录LeetCode刷题笔记-数据结构-day15108.将有序数组转换为二叉搜索树1.题目描述2.解题思路3.代码105.从前序与中序遍历序列构造二叉树1.题目描述2.解题思路3.代码103.二叉树的锯齿形层序遍历1.题目描述2.解题思路3.代码LeetCode刷... 查看详情
leetcode刷题笔记-数据结构-day6(代码片段)
文章目录LeetCode刷题笔记-数据结构-day6415.字符串相加1.题目描述2.解题思路3.代码409.最长回文串1.题目描述2.解题思路3.代码LeetCode刷题笔记-数据结构-day6415.字符串相加1.题目描述原题链接:415.字符串相加2.解题思路直接套用大... 查看详情
leetcode刷题笔记-数据结构-day11(代码片段)
文章目录LeetCode刷题笔记-数据结构-day11160.相交链表1.题目描述2.解题思路3.代码82.删除排序链表中的重复元素II1.题目描述2.解题思路3.代码LeetCode刷题笔记-数据结构-day11160.相交链表1.题目描述原题链接:160.相交链表2.解题思路... 查看详情
leetcode刷题笔记-数据结构-day18(代码片段)
文章目录LeetCode刷题笔记-数据结构-day18236.二叉树的最近公共祖先1.题目描述2.解题思路3.代码297.二叉树的序列化与反序列化1.题目描述2.解题思路3.代码LeetCode刷题笔记-数据结构-day18236.二叉树的最近公共祖先1.题目描述原题链接... 查看详情
leetcode刷题笔记-数据结构-day18(代码片段)
文章目录LeetCode刷题笔记-数据结构-day18236.二叉树的最近公共祖先1.题目描述2.解题思路3.代码297.二叉树的序列化与反序列化1.题目描述2.解题思路3.代码LeetCode刷题笔记-数据结构-day18236.二叉树的最近公共祖先1.题目描述原题链接... 查看详情
leetcode刷题笔记-数据结构-day18(代码片段)
文章目录LeetCode刷题笔记-数据结构-day18236.二叉树的最近公共祖先1.题目描述2.解题思路3.代码297.二叉树的序列化与反序列化1.题目描述2.解题思路3.代码LeetCode刷题笔记-数据结构-day18236.二叉树的最近公共祖先1.题目描述原题链接... 查看详情
leetcode刷题笔记-数据结构-day5(代码片段)
文章目录LeetCode刷题笔记-数据结构-day5334.递增的三元子序列1.题目描述2.解题思路3.代码238.除自身以外数组的乘积1.题目描述2.解题思路3.代码560.和为K的子数组1.题目描述2.解题思路3.代码LeetCode刷题笔记-数据结构-day5334.递增的三元... 查看详情
leetcode刷题笔记-数据结构-day7(代码片段)
文章目录LeetCode刷题笔记-数据结构-day790.单词规律1.题目描述2.解题思路3.代码763.划分字母区间1.题目描述2.解题思路3.代码LeetCode刷题笔记-数据结构-day790.单词规律1.题目描述原题链接:90.单词规律2.解题思路算法:哈希表... 查看详情
leetcode刷题笔记-数据结构-day9(代码片段)
文章目录LeetCode刷题笔记-数据结构-day9187.重复的DNA序列1.题目描述2.解题思路3.代码5.最长回文子串1.题目描述2.解题思路3.代码LeetCode刷题笔记-数据结构-day9187.重复的DNA序列1.题目描述原题链接:87.重复的DNA序列2.解题思路算法&... 查看详情
leetcode刷题笔记-数据结构-day10(代码片段)
文章目录LeetCode刷题笔记-数据结构-day102.两数相加1.题目描述2.解题思路3.代码142.环形链表II1.题目描述2.解题思路3.代码LeetCode刷题笔记-数据结构-day102.两数相加1.题目描述原题链接:2.两数相加2.解题思路直接模拟即可:从... 查看详情
leetcode刷题笔记-数据结构-day13(代码片段)
文章目录LeetCode刷题笔记-数据结构-day1325.K个一组翻转链表1.题目描述2.解题思路3.代码143.重排链表1.题目描述2.解题思路3.代码LeetCode刷题笔记-数据结构-day1325.K个一组翻转链表1.题目描述原题链接:25.K个一组翻转链表2.解题思... 查看详情