LeetCode中常见的堆排序

堆排序

今天在刷leetcode215题，碰到求解 TopK Elements问题，一共有三种方法，总结一下：

题目描述：

找到未排序数组中的第k个最大元素。请注意，它是排序顺序中的第k个最大元素，而不是第k个不同元素。

Input: [3,2,1,5,6,4] and k = 2  Output: 5
Input: [3,2,3,1,2,4,5,5,6]   and k = 4  Output: 4

解题方法：

1、对整个输入数组进行排序，然后通过它的索引（即O（1））操作访问该元素：

​ 时间复杂度 O(NlogN)，空间复杂度 O(1)。

public int findKthLargest(int[] nums, int k) {
        final int N = nums.length;
        Arrays.sort(nums);
        return nums[N - k];
}

2、堆排序也可以用于求解 Kth Element 问题，堆顶元素就是 Kth Element。使用面向最小值的优先级队列来存储第K个最大值。该算法迭代整个输入并维持优先级队列的大小。优先队列可以用堆来实现：

时间复杂度 O(NlogK)，空间复杂度 O(K)。

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();
}

3、基于切分partion的快速选择算法；快速排序的 partition() 方法，会返回一个整数 j 使得 a[l..j-1] 小于等于 a[j]，且 a[j+1..h] 大于等于 a[j]，此时 a[j] 就是数组的第 j 大元素。可以利用这个特性找出数组的第 k 个元素。

时间复杂度 最佳情况：O(N) 最坏情况：O（N ^ 2），空间复杂度 O(1)

我们如何才能改进上述解决方案并使其保证O（N）？答案非常简单，刚开始时要对数组进行洗牌shuffle，使其随机化输入，这样即使提供最坏情况输入，算法也不会受到影响。因此，所需要做的就是改变输入。

public int findKthLargest(int[] nums, int k) {

        shuffle(nums);//打乱数组
        k = nums.length - k;
        int lo = 0;
        int hi = nums.length - 1;
        while (lo < hi) {
            final int j = partition(nums, lo, hi);
            if(j < k) {
                lo = j + 1;
            } else if (j > k) {
                hi = j - 1;
            } else {
                break;
            }
        }
        return nums[k];
    }
//切分
 private int partition(int[] a, int lo, int hi) {

        int i = lo;
        int j = hi + 1;
        while(true) {
            while(i < hi && less(a[++i], a[lo]));
            while(j > lo && less(a[lo], a[--j]));
            if(i >= j) {
                break;
            }
            exch(a, i, j);
        }
        exch(a, lo, j);
        return j;
    }
//交换
    private void exch(int[] a, int i, int j) {
        final int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
//比较是否小于
    private boolean less(int v, int w) {
        return v < w;
    }

    private void shuffle(int a[]) {

        final Random random = new Random();
            for(int ind = 1; ind < a.length; ind++) {
                final int r = random.nextInt(ind + 1);
                exch(a, ind, r);
        }
    }

桶排序

Leetcode : 347. Top K Frequent Elements (Medium) 找出出现频率最多的 k 个数

题目描述：

给定非空的整数数组，返回k个最常见的元素。

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Input: nums = [1], k = 1
Output: [1]

解决方法：

设置若干个桶，每个桶存储出现频率相同的数，并且桶的下标代表桶中数出现的频率。

class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<>();
        for(int a : nums){
            map.put(a,map.getOrDefault(a,0)+1);//判断a是否存在，如果没出现

        }
        List<Integer> [] buckets = new ArrayList[nums.length + 1];
        for(int i : map.keySet()){
            int frequency = map.get(i);
            if(buckets[frequency]==null){
                buckets[frequency] = new ArrayList<>();

            }
            buckets[frequency].add(i);

        }
        List<Integer> topK = new ArrayList<>();
        //从后向前遍历桶，最先得到的 k 个数就是出现频率最多的的 k 个数
        for(int i = buckets.length - 1; i >= 0 && topK.size() < k;i--){
             if(buckets[i]!=null){
                 topK.addAll(buckets[i]);
             }   
        }
    return topK;
    }
}

荷兰国旗问题：

75. Sort Colors (Medium)

题目描述：

给定一个具有红色，白色或蓝色的n个对象的数组，对它们进行就地 排序，使相同颜色的对象相邻，颜色顺序为红色，白色和蓝色。

这里，我们将使用整数0,1和2分别表示红色，白色和蓝色。

注意： 您不应该使用库的排序功能来解决此问题。

Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

解决方法：

使用三向切分快速排序，将数组分成三个区间：等于红色、等于白色、等于蓝色。

class Solution {
    public void sortColors(int[] nums) {
        int zero = 0; int two = nums.length - 1; int one = 0;
        while(one <= two){
            if (nums[one] == 0){
                swap(nums,zero++,one++);//从前面开始交换的已经比较过了
            }else if (nums[one] == 2){
                swap(nums,two--,one);//这里注意one不要++，从后面交换到前面的还无法比较
            }else {
                one++;
            }
        }
    }
    private static void swap(int [] nums,int a,int b){
        int i = nums[a];
        nums[a] = nums[b];
        nums[b] = i;
    }
}