215. 数组中的第K个最大元素
| 在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。 示例 1: 输入: [3,2,1,5,6,4] 和 k = 2输出: 5 |
|---|
题解思路1：排序
public int findKthLargest(int[] nums, int k) {Arrays.sort(nums);return nums[nums.length - k];}
题解思路2：堆
class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> queue=new PriorityQueue<>();
for(int val:nums){
queue.offer(val);
if(queue.size()>k)
queue.poll();
}
return queue.peek();
}
}
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> pq = new PriorityQueue<>(); // 小顶堆
for (int val : nums) {
pq.add(val);
if (pq.size() > k) // 维护堆的大小为 K
pq.poll();
}
return pq.peek();
}
注：维持优先队列内的元素个数为k，那么第一个元素也就是原数组中的倒数第k个元素。
347. 前 K 个高频元素
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。示例 1: 输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2] |
|---|
题解思路：
1、遍历整个数组，并使用哈希表记录每个数字出现的次数。
2、根据出现的次数进行排序，建立小顶堆操作降低时间复杂度。
- 如果堆的元素个数小于k，就可以直接插入堆中
- 如果堆的元素个数等于k，检查大小，判断是否需要替换堆顶元素。
3、遍历小顶堆，获取前k个元素。
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> occurrences = new HashMap<Integer, Integer>();
for (int num : nums) {
occurrences.put(num, occurrences.getOrDefault(num, 0) + 1);
}
// int[] 的第一个元素代表数组的值，第二个元素代表了该值出现的次数
PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() {
public int compare(int[] m, int[] n) {
return m[1] - n[1];
}
});
for (Map.Entry<Integer, Integer> entry : occurrences.entrySet()) {
int num = entry.getKey(), count = entry.getValue();
if (queue.size() == k) {
if (queue.peek()[1] < count) {
queue.poll();
queue.offer(new int[]{num, count});
}
} else {
queue.offer(new int[]{num, count});
}
}
int[] ret = new int[k];
for (int i = 0; i < k; ++i) {
ret[i] = queue.poll()[0];
}
return ret;
}
}
注：1、创建优先队列
2、获取map集合的键值对集合
3、添加进优先队列时需要new
451. 根据字符出现频率排序
| 给定一个字符串，请将字符串里的字符按照出现的频率降序排列。 示例 1: 输入: “tree” 输出: “eert” 解释: ‘e’出现两次，’r’和’t’都只出现一次。 因此’e’必须出现在’r’和’t’之前。此外，”eetr”也是一个有效的答案。 |
|---|
题解思路1；堆
1、创建map统计元素以及对应出现的频次
2、创建大顶堆，将出现频次多的元素放在顶上
3、依次出队列，拼接结果
class Solution {
public String frequencySort(String s) {
//1、创建hashMap存储字符以及对应的频次
Map<Character,Integer> map=new HashMap<>();
for(char c:s.toCharArray()){
map.put(c,map.getOrDefault(c,0)+1);
}
//2、创建优先队列对频次进行排序操作
PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o2[1] - o1[1];
}
});
//3、将map中的结果一次装入大顶堆中
Set<Map.Entry<Character, Integer>> entries = map.entrySet();
for (Map.Entry<Character, Integer> entry : entries) {
char c=entry.getKey(); //字符
int num=entry.getValue(); //频次
queue.offer(new int[]{c,num}); //入队列
}
String res="";
//4、遍历获取结果
while(!queue.isEmpty()){
char c=(char)queue.peek()[0];
int num=queue.poll()[1];
while(num>0){
res+=c;
num--;
}
}
return res;
}
}
注：这种处理方式极为耗时
题解思路2：桶
1、创建map统计元素以及对应的频次
2、创建桶集合，按照频次放入对应的集合下标中
3、从后往前遍历桶集合，拼接结果集
Map<Character, Integer> map = new HashMap<>();
for (char c : s.toCharArray()) {
map.put(c, map.getOrDefault(c, 0) + 1);
}
//2、创建桶集合
List<List<Character>> bucket = new ArrayList<>();
for (int i = 0; i <=s.length(); i++) {
bucket.add(new ArrayList<>());
}
//3、遍历map存入桶集合中
for (char c : map.keySet()) {
int num = map.get(c);//获取频次也就是对应的哪个桶
bucket.get(num).add(c);
}
//4、从后往前遍历桶拼接结果
int size = bucket.size();
String res = "";
for (int i = size - 1; i >= 0; i--) {
if (bucket.get(i) != null) {
for (char c : bucket.get(i)) {
for(int j=0;j<i;j++){
res += c;
}
}
}
}
return res;
}
注：此处使用的桶结构为 List
public String frequencySort(String s) {
Map<Character, Integer> frequencyForNum = new HashMap<>();
for (char c : s.toCharArray())
frequencyForNum.put(c, frequencyForNum.getOrDefault(c, 0) + 1);
List<Character>[] frequencyBucket = new ArrayList[s.length() + 1];
for (char c : frequencyForNum.keySet()) {
int f = frequencyForNum.get(c);
if (frequencyBucket[f] == null) {
frequencyBucket[f] = new ArrayList<>();
}
frequencyBucket[f].add(c);
}
StringBuilder str = new StringBuilder();
for (int i = frequencyBucket.length - 1; i >= 0; i--) {
if (frequencyBucket[i] == null) {
continue;
}
for (char c : frequencyBucket[i]) {
for (int j = 0; j < i; j++) {
str.append(c);
}
}
}
return str.toString();
}
注：这里的代码和我的不同之处在于桶结构以及string的不同，但是时间花费似乎短很多。
75. 颜色分类
给定一个包含红色0、白色1和蓝色2，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。示例 1： 输入：nums = [2,0,2,1,1,0] 输出：[0,0,1,1,2,2] |
|---|
题解思路1：
1、统计每个数字出现的频次。
2、创建数组，根据每个数组的频次给数组赋值。
class Solution {
public void sortColors(int[] nums) {
int[] count=new int[3];
for(int i=0;i<nums.length;i++){
count[nums[i]]++;
}
int index=0;
for(int i=0;i<count[0];i++){
nums[index++]=0;
}
for(int i=0;i<count[1];i++){
nums[index++]=1;
}
for(int i=0;i<count[2];i++){
nums[index++]=2;
}
}
}
题解思路2：三路快排
1、创建三个指针：zero之前的数字全为0，one为移动比较的指针也代表之前的为1，two表示之后的全为2。
2、不断移动指针one，判断当前one的数值的大小从而进行相应的操作。
class Solution {
public void sortColors(int[] nums) {
int n=nums.length;
int l=0,index=0,r=n-1; //l和r代表了两个边界条件
while (index<=r){ //importment
if(nums[index]==0){
swap(nums,l,index);
l++;
index++;
}else if(nums[index]==1){
index++;
}else {
swap(nums,index,r);
r--;
}
}
}
private void swap(int[] nums,int i,int j){
int temp=nums[i];
nums[i]=nums[j];
nums[j]=temp;
}
}
注：1、遍历的截止条件
题解思路3：遍历赋值
1、先对数组进行排序操作，保证遍历的顺序是从下到大进行
1、依旧是创建三个指针，当数值为1时，三个指针都向前移动，且指针0赋值
2、指针1与指针2进行相同的操作即可。
class Solution {
public void sortColors(int[] nums) {
Arrays.sort(nums);
int num0 = 0;
int num1 = 0;
int num2 = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == 0) {
num2++;
num1++;
nums[num0++] = 0;
} else if (nums[i] == 1) {
num2++;
nums[num1++] = 1;
} else {
nums[num2++] = 2;
}
}
}
}
总结
1、求解TopK Elements问题，也就是k个最下元素的问题，使用最小堆（大顶堆）来实现。实现过程：不断地往大顶堆中插入新元素，当堆中元素的数量大于 k 时，移除堆顶元素，也就是当前堆中最大的元素，剩下的元素都为当前添加过的元素中最小的 K 个元素。插入和移除堆顶元素的时间复杂度都为 log2N。
2、求解频次问题排序，可以考虑使用桶集合来实现。桶元素的索引下标就是频次的大小。
若有收获，就点个赞吧
0 人点赞
