跳至主要內容

第9章 堆

Weiser算法堆大约 5 分钟

第9章 堆

剑指offerⅡ59：数据流最大的k个值

设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。

请实现 KthLargest 类：

  • KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。
  • int add(int val) 将 val 插入数据流 nums 后，返回当前数据流中第 k 大的元素。
class KthLargest {
    PriorityQueue<Integer> minP;
    int size;

    public KthLargest(int k, int[] nums) {
        minP = new PriorityQueue<>((a, b) -> a - b);
        size = k;
        for (int num : nums) {
            add(num);
        }
    }

    public int add(int val) {
        if (minP.size() < size) {
            minP.add(val);
        } else if (minP.peek() < val) {
            minP.add(val);
            minP.poll();
        }
        return minP.peek();
    }
}

剑指offerⅡ60：出现频率最高的k个数字

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

示例 1:

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

示例 2:

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

算法：

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> num2count = new HashMap<>();
        PriorityQueue<Map.Entry<Integer, Integer>> minHeap = new PriorityQueue<>((a, b) -> (a.getValue() - b.getValue()));
        for (int num : nums) {
            num2count.put(num, num2count.getOrDefault(num, 0) + 1);
        }
        for (Map.Entry<Integer, Integer> map : num2count.entrySet()) {
            if (minHeap.size() < k) {
                minHeap.add(map);
            } else {
                if (map.getValue() > minHeap.peek().getValue()) {
                    minHeap.add(map);
                    minHeap.poll();
                }
            }
        }
        int[] ans = new int[k];
        for (int i = 0; i < k; i++) {
            ans[i] = minHeap.poll().getKey();
        }
        return ans;
    }
}

剑指offerⅡ61：和最小的k个数对

给定两个以升序排列的整数数组 nums1 和 nums2 , 以及一个整数 k 。

定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2 。

请找到和最小的 k 个数对 (u1,v1), (u2,v2) ... (uk,vk) 。

示例 1:

输入: nums1 = [1,1,2], nums2 = [1,2,3], k = 2
输出: [1,1],[1,1]
解释: 返回序列中的前 2 对数：
     [1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]

示例 2:

输入: nums1 = [1,2], nums2 = [3], k = 3 
输出: [1,3],[2,3]
解释: 也可能序列中所有的数对都被返回:[1,3],[2,3]

方法一：大根堆

下面是自己写的错误代码，错误的地方在于：将所有的数对之和计算出来，然后以数对为key，以和为value，全都放到map中，但是key是唯一的，这样会替换掉相同的答案。

class Solution {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<List<Integer>> ans = new ArrayList<>();
        List<List<Integer>> combinitions = new ArrayList<>();
        for (int num1 : nums1) {
            for (int num2 : nums2) {
                List<Integer> combinition = new ArrayList<>();
                combinition.add(num1);
                combinition.add(num2);
                combinitions.add(combinition);
            }
        }
        Map<List<Integer>, Integer> list2count = new HashMap<>();
        for (List<Integer> combinition : combinitions) {
            list2count.put(combinition, combinition.get(0) + combinition.get(1));
        }
        Queue<Map.Entry<List<Integer>, Integer>> maxHeap = new PriorityQueue<>((a, b) -> (b.getValue() - a.getValue()));
        for (Map.Entry<List<Integer>, Integer> map : list2count.entrySet()) {
            if (maxHeap.size() < k) {
                maxHeap.add(map);
            } else {
                if (map.getValue() < maxHeap.peek().getValue()) {
                    maxHeap.add(map);
                    maxHeap.poll();
                }
            }
        }
        for (int i = 0; i < k; i++) {
            if(!maxHeap.isEmpty())
                ans.add(maxHeap.poll().getKey());
        }
        return ans;
    }
}

将上面的错误代码改正：一边计算数对之和，一边将其与堆顶比较，然后考虑是否放入其中。

局限性：两个数组是增序排列的，没有必要全部遍历，否则耗费时间太长。

class Solution {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<List<Integer>> ans = new ArrayList<>();
        List<List<Integer>> combinitions = new ArrayList<>();
        for (int num1 : nums1) {
            for (int num2 : nums2) {
                List<Integer> combinition = new ArrayList<>();
                combinition.add(num1);
                combinition.add(num2);
                combinitions.add(combinition);
            }
        }

        Map<List<Integer>, Integer> list2count = new HashMap<>();
        Queue<Map.Entry<List<Integer>, Integer>> maxHeap = new PriorityQueue<>((a, b) -> (b.getValue() - a.getValue()));
        for (List<Integer> combinition : combinitions) {
            list2count.put(combinition, combinition.get(0) + combinition.get(1));
            for (Map.Entry<List<Integer>, Integer> map : list2count.entrySet()) {
                if (maxHeap.size() < k) {
                    maxHeap.add(map);
                } else {
                    if (map.getValue() < maxHeap.peek().getValue()) {
                        maxHeap.add(map);
                        maxHeap.poll();
                    }
                }
            }
            list2count.remove(combinition);
        }

        for (int i = 0; i < k; i++) {
            if(!maxHeap.isEmpty())
                ans.add(maxHeap.poll().getKey());
        }
        return ans;
    }
}

继续改进自己的方法，改进的地方在于：

1. 不用一次性计算出所有数对的和，一边遍历，一边计算，同时检验能不能加入大根堆

2. 不用遍历所有数字

class Solution {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<List<Integer>> ans = new ArrayList<>();
        Queue<List<Integer>> maxHeap = new PriorityQueue<>((a, b) -> (b.get(0) + b.get(1) - a.get(0) - a.get(1)));
        for (int num1 : nums1) {
            for (int num2 : nums2) {
                ArrayList<Integer> combinition = new ArrayList<>();
                combinition.add(num1);
                combinition.add(num2);
                //System.out.println(combinition.toString());
                if (maxHeap.size() < k) {
                    maxHeap.add(combinition);
                } else {
                    if (combinition.get(0) + combinition.get(1) < maxHeap.peek().get(0) + maxHeap.peek().get(1)) {
                        maxHeap.remove(maxHeap.peek());
                        maxHeap.offer(combinition);
                    }
                }
            }
        }

        while (!maxHeap.isEmpty())
            ans.add(maxHeap.poll());

        return ans;
    }
}

class Solution {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<List<Integer>> ans = new ArrayList<>();
        Queue<List<Integer>> maxHeap = new PriorityQueue<>((a, b) -> (b.get(0) + b.get(1) - a.get(0) - a.get(1)));
        for (int i = 0; i < Math.min(k, nums1.length); i++) {
            for (int j = 0; j < Math.min(k, nums2.length); j++) {
                ArrayList<Integer> combinition = new ArrayList<>();
                combinition.add(nums1[i]);
                combinition.add(nums2[j]);

                if (maxHeap.size() < k) {
                    maxHeap.add(combinition);
                } else {
                    if (combinition.get(0) + combinition.get(1) < maxHeap.peek().get(0) + maxHeap.peek().get(1)) {
                        maxHeap.remove(maxHeap.peek());
                        maxHeap.offer(combinition);
                    }
                }
            }
        }

        while (!maxHeap.isEmpty())
            ans.add(maxHeap.poll());

        return ans;
    }
}

但是复杂度有25%，35%，仍然需要改进。

方法二：小根堆（更难）

class Solution {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<List<Integer>> ans = new ArrayList<>();
        Queue<int[]> maxHeap = new PriorityQueue<>((a, b) -> (nums1[a[0]] + nums2[a[1]] - nums1[b[0]] - nums2[b[1]]));
        for (int i = 0; i < Math.min(k, nums1.length); i++) {
            maxHeap.add(new int[]{i, 0});
        }
        //弹出k个结果，要么堆为空停止
        while (k-- > 0 && !maxHeap.isEmpty()) {
            int index[] = maxHeap.poll();
            int i = index[0];
            int j = index[1];
            //弹出一个最小的结果放进答案中。
            ans.add(Arrays.asList(nums1[i], nums2[j]));
            //观察能不能放入再将一个可能的结果放入最小堆中，作为候选者。
            if (j + 1 < nums2.length) {
                maxHeap.add(new int[]{i, j + 1});
            }
        }
        return ans;
    }
}

LC295：数据流的中位数

中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。

例如，

[2,3,4] 的中位数是 3

[2,3] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构：

  • void addNum(int num) - 从数据流中添加一个整数到数据结构中。
  • double findMedian() - 返回目前所有元素的中位数。
class MedianFinder {
    PriorityQueue<Integer> maxHeap;
    PriorityQueue<Integer> minHeap;
    /** initialize your data structure here. */
    public MedianFinder() {
        maxHeap = new PriorityQueue<>((a, b) -> (b - a));
        minHeap = new PriorityQueue<>();
    }
    
    public void addNum(int num) {
        if (maxHeap.size() == minHeap.size()) {
            maxHeap.add(num);
            minHeap.add(maxHeap.poll());
        } else {
            minHeap.add(num);
            maxHeap.add(minHeap.poll());
        }
    }
    
    public double findMedian() {
        return (maxHeap.size() + minHeap.size()) % 2 == 0 ?
                (maxHeap.peek() + minHeap.peek()) / 2.0 :
                minHeap.peek();
    }
}
默认页脚
Copyright © 2023 Weiser