算法题--topN问题

topN问题：思路：排序，优先队列，map

1、前k个高频元素

题目：

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:

输入: nums = [1], k = 1
输出: [1]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/top-k-frequent-elements

思路：

使用map储存元素与出现的次数，然后按照出现次数作为优先级，将元素储存到优先级队列中，随后输出队列的前k个元素即可。

代码：

package com.example.demo.core.Leecode;
import java.util.Arrays;
import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.Set;
/**
 * @author: HanXu
 * on 2022/2/22
 * Class description: topN问题
 */
public class TopN {
    public static void main(String[] args) {
        int[] arr = {1, 1, 1, 2, 2, 3};
        int n = 2;
        System.out.println(Arrays.toString(topKFrequent(arr, n)));
    }
    /**
     * 前k个高频元素：给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
     * 使用map储存元素与出现的次数，然后按照出现次数作为优先级，将元素储存到优先级队列中，随后输出队列的前k个元素即可。
     * @param nums
     * @param k
     * @return
     */
    public static int[] topKFrequent(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }
        //存的时候，按照出现次数从大到小排序
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(((o1, o2) -> (map.get(o2) - map.get(o1))));
        Set<Integer> keySet = map.keySet();
        for (Integer key : keySet) {
            priorityQueue.offer(key);
        }
        //取出前k个元素
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = priorityQueue.poll();
        }
        return result;
    }
}

2、数组中的第K个最大元素

题目：

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array

思路：

根据示例2可以看出来，相同的元素不被认为是同一个最大元素，两个5分别是第2大、第3大元素

• 直接排序，然后输出length-k索引位置的元素。
• 使用优先队列，储存元素时按照从大到小排序，然后清除队列中的前k-1个元素，返回头部元素就是第k个最大元素。

代码：

package com.example.demo.core.Leecode;
import java.util.Arrays;
import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.Set;
/**
 * @author: HanXu
 * on 2022/2/22
 * Class description: 
 */
public class TopN {
    public static void main(String[] args) {
        int[] arr = {3, 2, 3, 1, 2, 4, 5, 5, 6};
        int k = 4;
//        System.out.println(findKthLargest1(arr, k));
        System.out.println(findKthLargest2(arr, k));
    }
    /**
     * 数组中的第K个最大元素：给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
     * @param nums
     * @param k
     * @return
     */
    public static int findKthLargest1(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length - k];
    }
    public static int findKthLargest2(int[] nums, int k) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(((o1, o2) -> (o2 - o1)));
        for (int i = 0; i < nums.length; i++) {
            priorityQueue.add(nums[i]);
        }
        for (int i = 0; i < k - 1; i++) {
            priorityQueue.remove();
        }
        return priorityQueue.poll();
    }
}