如何降低商品增选任务代码时间复杂度 修正优先队列实现错误

问题根因 #

你修改后的代码错误核心在于逻辑和需求不匹配：需求要求每次Select操作取当前所有已添加商品重新排序后的第k位（k是累计执行过的Select次数，从0开始计数，每次Select后自增），而你修改后的代码每次将最小元素弹出后直接丢弃，相当于取历史第k小的元素，当后续新增比历史已选元素更小的商品时，自然会出现结果错误。
比如示例1中第一次Select取出Ball后直接丢弃，后续新增了更便宜的Pen，第二次Select就会取到Pen，和需求要求的取全量排序后第1位的Ball不符。

优化方案：双堆维护，时间复杂度O(n log n) #

我们可以用两个优先队列来维护状态，避免每次Select都全量重新排序：

• 大顶堆left：存储排序后前m个最小的元素，m是已经执行过的Select次数，堆顶是前m个元素里最大的那个（也就是上一次Select取到的元素）
• 小顶堆right：存储剩余的所有元素，堆顶就是下一次Select需要取的第m位元素

操作规则 #

1. Add操作：
   • 如果left不为空且当前商品比left堆顶元素小，加入left，否则加入right
   • 调整两个堆的大小，保证left的大小永远等于已执行的Select次数m：如果left大小超过m，就把left堆顶元素移到right中
2. Select操作：
   • 直接把right的堆顶元素移到left中，这个元素就是当前要取的第m位结果，加入返回列表
   • 已执行Select次数m自增1

正确实现代码 #

import java.util.*;

public class ItemProcess {

    static class Item implements Comparable<Item> {
        int price;
        String name;

        public Item(String name, String p) {
            this.name = name;
            this.price = Integer.parseInt(p);
        }

        public int compareTo(Item item) {
            int c = price - item.price;
            if (c == 0)
                c = name.compareTo(item.name);
            return c;
        }
    }

    public static List<String> process(List<List<String>> input) {
        List<String> result = new ArrayList<>();
        // left是大顶堆，存前m个最小元素，堆顶是前m个里最大的
        PriorityQueue<Item> left = new PriorityQueue<>(Collections.reverseOrder());
        // right是小顶堆，存剩余元素，堆顶是下一个要取的元素
        PriorityQueue<Item> right = new PriorityQueue<>();
        // m是已经执行的Select次数
        int m = 0;

        for (List<String> op : input) {
            if ("Add".equals(op.get(0))) {
                Item item = new Item(op.get(1), op.get(2));
                if (!left.isEmpty() && item.compareTo(left.peek()) < 0) {
                    left.add(item);
                } else {
                    right.add(item);
                }
                // 调整left大小永远等于m
                if (left.size() > m) {
                    right.add(left.poll());
                }
            } else {
                // Select操作，取right堆顶
                Item selectItem = right.poll();
                result.add(selectItem.name);
                left.add(selectItem);
                m++;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        // 示例1测试
        List<List<String>> input1 = Arrays.asList(
                Arrays.asList("Add", "Apple", "4"),
                Arrays.asList("Add", "Ball", "3"),
                Arrays.asList("Select", "", ""),
                Arrays.asList("Add", "Toy", "5"),
                Arrays.asList("Add", "Pen", "1"),
                Arrays.asList("Select", "", "")
        );
        System.out.println(process(input1)); // 输出 [Ball, Ball]

        // 示例2测试
        List<List<String>> input2 = Arrays.asList(
                Arrays.asList("Add", "Apple", "4"),
                Arrays.asList("Add", "Ball", "3"),
                Arrays.asList("Select", "", ""),
                Arrays.asList("Select", "", ""),
                Arrays.asList("Add", "Toy", "5"),
                Arrays.asList("Select", "", "")
        );
        System.out.println(process(input2)); // 输出 [Ball, Apple, Toy]
    }
}

内容的提问来源于stack exchange，提问作者Learner