标签： 优先队列

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2：

输入：lists = []
输出：[]

示例 3：

输入：lists = [[]]
输出：[]

提示：

• k == lists.length
• 0 <= k <= 10^4
• 0 <= lists[i].length <= 500
• -10^4 <= lists[i][j] <= 10^4
• lists[i] 按 升序 排列
• lists[i].length 的总和不超过 10^4

JAVA 分治归并 其实挺简单的

1. 对于K个链表，可以两两合并（有点归并排序的意思）
2. 一次合并完了之后此时变成K/2个链表了，对剩下的链表继续两两合并
3. 最终全都合并到了一个链表里
4. 至于两个链表的合并过程，直接参考剑指Offer25题，比较简单算链表基本题了吧，我之前写的题解双指针合并，不如找两串珠子自己比划比划
5. 至于如何选择两两的过程可以简单设计下

//对应为k个链表在入参数组中的下标
1 [0,1],[2,3],[4,5],[6,7],[8]
2 [0,2],[4,6],[8]
4 [0,4],[8]
8 [0,8]

- 第一次 `[0,1],[2,3],[4,5],[6,7]`互相合并，结果留在第一个链表位置， `[8]`单独拉下了没关系先留着
- 第二次 `[0,2],[4,6]` 互相合并，结果存在0 , 4 位置，8继续留着，`[8]`没关系
- 第三次 再次合并`[0,4]`，`[8]`继续留着
- 最后一次合并`[0,8]`结束收工

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 1){
            return lists[0];
        }
        if (lists.length == 0){
            return null;
        }
        int dis = 1;
        while (dis < lists.length){
            //1 [0,1],[2,3],[4,5],[6,7],[8]
            //2 [0,2],[4,6],[8]
            //4 [0,4],[8]
            //8 [0,8]
            for (int i = 0; i + dis < lists.length; i += dis*2) {
                //合并两个有序链表  剑指Offer25题
                lists[i] = mergeTwoLists(lists[i],lists[i+dis]);
                lists[i+dis] = null;
            }
            dis *=2;
        }
        return lists[0];
    }

    public ListNode mergeTwoLists(ListNode l1, ListNode l2){
        ListNode head = new ListNode();
        ListNode cur = head;
        while ( l1 != null || l2 != null ){
            if (l1 == null || l2 == null){
                cur.next = l1==null?l2:l1;
                break;
            }
            if (l1.val < l2.val){
                cur.next = l1;
                l1 = l1.next;
            }else{
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        return head.next;
    }
}

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

例如，

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

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

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

• void addNum(int num) – 从数据流中添加一个整数到数据结构中。
• double findMedian() – 返回目前所有元素的中位数。

示例 1：

输入：
["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
[[],[1],[2],[],[3],[]]
输出：[null,null,null,1.50000,null,2.00000]

示例 2：

输入：
["MedianFinder","addNum","findMedian","addNum","findMedian"]
[[],[2],[],[3],[]]
输出：[null,null,2.00000,null,2.50000]

限制：

• 最多会对 addNum、findMedian 进行 50000 次调用。

注意：本题与主站 295 题相同：https://leetcode-cn.com/problems/find-median-from-data-stream/

【双薯片桶算法】又见薯片桶

本来其实看到困难题有点多想，不过回想了下之前做的这题，我的题解剑指 Offer 09. 用两个栈实现队列（简单） ， 再想想这题，好像….也没那么复杂了

借一次之前的图

我们需要的其实是一个队列。但是和之前不同的是这次是有序的，我们要从这个有序队列中取中间那个值。

这样，我们把原来的两个栈换成两个堆，一个大顶堆，一个小顶堆，那么对应这上面这个图

1. 左边一个大顶堆，堆顶是最大值
2. 右边一个小顶堆，堆顶是最小值
3. 每插入一个值的时候判断下是应该往左边的插还是往右边插，小于等于左边的最大值，就往左边插，大于等于右边的最小值，就往右边插，只要做一个判断即可
4. 插入之后对两个堆做一下平衡，保证左边堆的数量等于右边堆的数量，或者等于右边堆的数量加1，就如同上面的两个薯片桶从左往右倒一个，或者从右往左倒一个
5. 不同于之前的栈维护的队列，堆附带自动排序的属性，所以你可以认为把一个数字插入其中一个堆里的时候，可以自动将他排序到对应的正确位置，这是一个比较智能的薯片桶

代码

class MedianFinder {

    PriorityQueue<Integer> left;
    PriorityQueue<Integer> right;

    /** initialize your data structure here. */
    public MedianFinder() {
        left = new PriorityQueue<>((a,b)-> b-a);
        right = new PriorityQueue<>();
    }
    
    public void addNum(int num) {
        if (left.size()==0||num<=left.peek()){
            left.offer(num);
        }else{
            right.offer(num);
        }
        if (left.size() - right.size()>1){
            right.offer(left.poll());
        }else if (right.size() > left.size()){
            left.offer(right.poll());
        }
    }
    
    public double findMedian() {
        if (left.size() == right.size()){
            return ((double) (left.peek() + right.peek()))/2;
        }else{
            return (double)left.peek();
        }
    }
}

假设 力扣（LeetCode）即将开始 IPO 。为了以更高的价格将股票卖给风险投资公司，力扣 希望在 IPO 之前开展一些项目以增加其资本。 由于资源有限，它只能在 IPO 之前完成最多 k 个不同的项目。帮助 力扣 设计完成最多 k 个不同项目后得到最大总资本的方式。

给你 n 个项目。对于每个项目 i ，它都有一个纯利润 profits[i] ，和启动该项目需要的最小资本 capital[i] 。

最初，你的资本为 w 。当你完成一个项目时，你将获得纯利润，且利润将被添加到你的总资本中。

总而言之，从给定项目中选择 最多 k 个不同项目的列表，以 最大化最终资本 ，并输出最终可获得的最多资本。

答案保证在 32 位有符号整数范围内。

示例 1：

输入：k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]
输出：4
解释：
由于你的初始资本为 0，你仅可以从 0 号项目开始。
在完成后，你将获得 1 的利润，你的总资本将变为 1。
此时你可以选择开始 1 号或 2 号项目。
由于你最多可以选择两个项目，所以你需要完成 2 号项目以获得最大的资本。
因此，输出最后最大化的资本，为 0 + 1 + 3 = 4。

示例 2：

输入：k = 3, w = 0, profits = [1,2,3], capital = [0,1,2]
输出：6

提示：

• 1 <= k <= 105
• 0 <= w <= 109
• n == profits.length
• n == capital.length
• 1 <= n <= 105
• 0 <= profits[i] <= 104
• 0 <= capital[i] <= 109

题解

从题面来理解，第一步，从所有项目中找到本金小于等于当前拥有的总的本金的项目，这些项目为可投资项目。第二步，由于给出的是纯利润，且题面并没有要求说本金最大化优化使用，那么就可以最简单的直接选利润最大的一个项目来投，等利润拿到了，再去投资下一个项目。

而如果要求本金最大化优化使用的话，可能要考虑一次投资多个项目，什么样的项目组合能得到最大化利润，这样的要求就更加复杂话了，而实际的企业投资操作比这个更加复杂，更多的风险控制，不是什么能套个公式算算能到结论的。

好的，既然上面思路理出来了，我们知道提供出来的profits和capital是索引对应关系，所以第一步的操作中，可以维护一个堆，堆的内容和capital的索引和本金的值，这样取的时候从顶部取出所有小于当前拥有的本金的值。

接下来第二步，前面我们已经拿到了所有的符合投资要求的索引了，所以这里，我们对应的也建一个堆，按照profits利润值降序排列。然后从顶部取出一个，算出新的总的本金金额。

到这里编码思路就已经出来了。

class Solution {
    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        int amount = w;
        //堆1成本降序
        //内部结构[0:索引，1:成本]
        //堆1中目前成本越小的越排在前面，便于下一步寻找符合成本要求的项目
        PriorityQueue<int[]> queue1 = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1]-o2[1];
            }
        });
        for (int i = 0; i < capital.length; i++) {
            queue1.offer(new int[]{i,capital[i]});
        }

        //queue2
        //int[0] 成本  int[1]利润  利润越大的越在前面
        PriorityQueue<int[]> queue2 = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o2[1]-o1[1];
            }
        });

        while (k>0){
            while (!queue1.isEmpty() && queue1.peek()[1] <= amount){
                //arr[0]索引位，arr[1]是成本位
                int[] arr = queue1.poll();
                queue2.offer(new int[]{arr[1],profits[arr[0]]});
            }
            if (queue2.isEmpty()){
                //没有能投的项目了，钱.......不够
                break;
            }
            int[] arr2 = queue2.poll();
            k--;
            //赚了 arr2[1]
            amount +=arr2[1];
        }
        return amount;
    }
}

那么，你学废了嘛！~

设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。

示例：

输入： arr = [1,3,5,7,2,4,6,8], k = 4
输出： [1,2,3,4]

提示：

• 0 <= len(arr) <= 100000
• 0 <= k <= min(100000, len(arr))

题解，9月3日的每日一题

看到题目第一反应，找一组无序数字中的最小，或者最大的几个，典型的用堆来解决的问题，不过在写堆之前，可以尝试自己写一个类似的逻辑的代码。

维护一个长度为k的有序数组，遍历原数组，挨个将数组中的值加入到维护的k长度数组中，在加入的时候，判断这个值和数组中已有值的大小关系，将这个值插入到k的对应位置，保持数组k的单调性。如果长度k的数组加入值的时候长度将会超过k，则移除掉末尾的最大值。

class Solution {
    int[] list;
    int listCount = 0;
    public int[] smallestK(int[] arr, int k) {
        if (k == 0){
            return new int[0];
        }
        list = new int[k];
        Arrays.fill(list,Integer.MIN_VALUE);

        for (int i = 0; i < arr.length; i++) {
            if (listCount < list.length){
                //此时list还没满
                listAdd(arr[i]);
            }else{
                listInsert(arr[i]);
            }
        }

        return list;

    }

    public void listAdd( int num ){
        if (listCount == 0){
            list[0] = num;
            listCount++;
            return;
        }
        //比如
        //[1,2,4,5,6]找到4比3大
        //[1,2,3,4,5,6]把4、5、6往后挪移一位在4的位置插入
        for (int i = 0; i < list.length; i++) {
            if (list[i] > num){
                System.arraycopy(list,i,list,i+1,listCount-i);
                list[i] = num;
                listCount++;
                return;
            }
        }
        list[listCount] = num;
        listCount++;
    }

    public void listInsert( int num ){
        for (int i = 0; i < list.length; i++) {
            if (list[i] > num){
                System.arraycopy(list,i,list,i+1,list.length-i-1);
                list[i] = num;
                break;
            }
        }
    }
}

在这个代码中，比如原数组[1,2,4,5,6]，想把[4,5,6]往后移动一位，需要从末位开始往前遍历移动，例如，把6先移动到索引5的位置，再移动5到索引4的位置，再移动3。如果是从前面开始，先移动4，则会覆盖到5的位置，导致后面想移动5的时候，5已经不存在了被4覆盖掉了。这边我原本一开始是这么写的逻辑，不过提交的时候，emmm，超时了…….，这样的有序排列的结果移动复制的方法，可以保证在多出k个的时候能自动将最大值移出数组。

所以大概回顾了下整个的代码逻辑，最耗时的部分好像在这个复制的地方，那么修改一下，使用System.arraycopy这个native方法来代替原来自己写的for循环。确实可以过了。结果如下，在超时的边缘不断疯狂尝试。

解答成功:
执行耗时:1821 ms,击败了5.37% 的Java用户
内存消耗:47.9 MB,击败了55.67% 的Java用户

嗯，想一下哪边能有优化的呢，原来的复制部分的问题用System.arraycopy处理了，接下来看起来应该是在数组内查找的地方可以优化。这里可以改成二分，找到第一个比当前值大的值的索引。

堆实现

这里我们先直接改成堆试试看

class Solution {
    public int[] smallestK(int[] arr, int k) {
        if (k == 0){
            return new int[0];
        }
        PriorityQueue<Integer> queue = new PriorityQueue<>(Comparator.comparingInt(o -> o));
        for (int j : arr) {
            queue.add(j);
        }
        int[] list = new int[k];
        int count = 0;
        while (!queue.isEmpty() && count <k){
            list[count] = queue.poll();
            count++;
        }
        return list;
    }
}

解答成功:
执行耗时:19 ms,击败了38.21% 的Java用户
内存消耗:46.5 MB,击败了87.38% 的Java用

接下来，另一个思路，先排序，排序后取前面k个结果返回，先撸一版代码，直接先调用API来试试

class Solution2 {
    public int[] smallestK(int[] arr, int k) {
        if (k == 0){
            return new int[0];
        }
        int[] list = new int[k];
        Arrays.sort(arr);
        System.arraycopy(arr,0,list,0,k);
        return list;

    }
}

解答成功:
执行耗时:6 ms,击败了70.64% 的Java用户
内存消耗:48.2 MB,击败了20.73% 的Java用户

emmm这速度可以啊