java中不用优先队列求最大的k个数

一种不用优先队列求最大的k个数的方法是使用快速排序（QuickSort）算法。

具体步骤如下：

1. 选取数组中任意一个数作为基准数（pivot）。

2. 将数组中小于基准数的数放在基准数的左侧，大于基准数的数放在右侧。

3. 重复步骤2，直到左侧数组的长度大于等于k。

4. 返回左侧数组中的最大的k个数。

由于快速排序算法的时间复杂度为O(nlogn)，因此该方法的时间复杂度为O(nlogn)。

相关问题

给定一个数组，求前k个最大的数，Java实现

可以使用最小堆来实现求前k个最大的数，具体步骤如下：

1. 建立一个大小为k的最小堆，堆中存放数组中前k个数；
2. 从第k+1个数开始遍历数组，如果当前数比最小堆的堆顶元素大，则将堆顶元素弹出，将当前数插入到堆中；
3. 遍历完整个数组后，最小堆中剩余的k个元素即为前k个最大的数。

Java代码如下：

import java.util.PriorityQueue;

public class TopK {
    public static int[] topK(int[] nums, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<>(k);
        for (int i = 0; i < k; i++) {
            queue.offer(nums[i]);
        }
        for (int i = k; i < nums.length; i++) {
            if (nums[i] > queue.peek()) {
                queue.poll();
                queue.offer(nums[i]);
            }
        }
        int[] result = new int[k];
        int i = 0;
        for (int num : queue) {
            result[i++] = num;
        }
        return result;
    }
}

其中，PriorityQueue是Java中的优先队列，它默认是一个最小堆。在上述代码中，我们建立了一个最小堆，将数组中前k个数加入堆中。然后，从第k+1个数开始遍历数组，如果当前数比堆顶元素大，则将堆顶元素弹出，将当前数插入堆中。最后，将最小堆中剩余的k个元素取出，即为前k个最大的数。

java 实现k排序

K排序是一种将一个数组分成K个块，然后对每个块内的元素进行排序，最后将整个数组进行合并的排序算法。在实现时可以采用归并排序的思想，将每个块内的元素进行排序后再进行合并。

以下是Java实现K排序的示例代码：

public class KSort {

    public static void main(String[] args) {
        int[] arr = {3, 2, 1, 6, 5, 4, 9, 8, 7};
        kSort(arr, 3);
        System.out.println(Arrays.toString(arr));
    }

    public static void kSort(int[] arr, int k) {
        int n = arr.length;
        int blockSize = (n + k - 1) / k; // 每个块的大小
        for (int i = 0; i < k; i++) {
            int left = i * blockSize;
            int right = Math.min((i + 1) * blockSize, n);
            Arrays.sort(arr, left, right);
        }
        merge(arr, k, blockSize);
    }

    public static void merge(int[] arr, int k, int blockSize) {
        int[] res = new int[arr.length];
        PriorityQueue<Node> pq = new PriorityQueue<>();
        for (int i = 0; i < k; i++) {
            int left = i * blockSize;
            int right = Math.min((i + 1) * blockSize, arr.length);
            if (left < right) {
                pq.offer(new Node(left, right, arr[left]));
            }
        }
        int idx = 0;
        while (!pq.isEmpty()) {
            Node node = pq.poll();
            res[idx++] = node.val;
            node.left++;
            if (node.left < node.right) {
                node.val = arr[node.left];
                pq.offer(node);
            }
        }
        System.arraycopy(res, 0, arr, 0, arr.length);
    }

    static class Node implements Comparable<Node> {
        int left, right, val;

        public Node(int left, int right, int val) {
            this.left = left;
            this.right = right;
            this.val = val;
        }

        @Override
        public int compareTo(Node o) {
            return Integer.compare(val, o.val);
        }
    }
}

在上面的代码中，我们首先将数组分成了K个块，每个块的大小为n/k，然后对每个块进行排序。接着，我们使用优先队列来实现归并排序的合并过程，将每个块内的元素按顺序加入到优先队列中，然后每次从队列中取出最小的元素加入到结果数组中，同时将该元素所在块的下一个元素加入到队列中，直到队列为空为止。最后将结果数组复制回原数组即可。

示例代码中采用了一个Node类来表示块内的元素，其中left和right分别表示该元素在原数组中的左右下标，val表示该元素的值。优先队列中按照元素值的大小进行比较，以保证每次取出的元素都是块内最小的元素。