Leetcode- 347( 桶排序 或 快排思想)_leetcode347

题目链接 LeetCode-347
题目描述
给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

示例 1:

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

思路一

根据自己的做法，使用一个列为2的二维数组来存储 <元素, 个数>。
根据二维数组的第二列(元素个数), 利用快速排序对二维数组进行排序。
取出二维数组中前 k 的 元素值即可。
AC代码 :

class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        List<Integer> list = new ArrayList<>();
        Arrays.sort(nums, 0, nums.length);
        int[][] count = new int[nums.length][2];
        int len = 0, l = 0;
        for(int i = 0; i < nums.length-1; i++) {
        	if(nums[i] != nums[i+1]) {
        		count[len][0] = nums[i];
        		count[len][1] = i+1-l;
        		l = i+1;
        		len++;
        	}
        }
        count[len][0] = nums[nums.length-1];
        count[len][1] = nums.length - l;
        len++;

        q_sort(count, 0, len-1);

        for(int i = len-1; i > len-1-k; i--) {
        	list.add(count[i][0]);
        }
        return list;
    }

    public void q_sort(int[][] nums, int l, int r) {
        if(l >= r) return;
        int i = l;
        int j = r;
        while (l < r) {
            while (nums[l][1] <= nums[i][1] && l < j) l++;
            while (nums[r][1] > nums[i][1] &&
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32