前言

刷算法题的时候经常遇到这样一个情景:

仅遍历一趟，找出所有 "特殊数字" 并且按照从大到小顺序输出

假设 "特殊数字" 的要求如下:

java
 代码解读
复制代码
public boolean isSpecial(int num) {
    if(//some conditions) {
        return true;
    }
    return false;
}

"特殊数字" 的总数量并不知道。无法提前构造数组大小存储所有“特殊数字” 后借助 Arrays.sort() 排序。

有啥比较好的方法吗?

方法 01 - 使用优先级队列(堆)

利用 Java 的 PriorityQueue，配合最大堆实现从大到小排序。

步骤

• 使用 PriorityQueue 并指定一个降序比较器。
• 遍历时将每个"特殊数字"加入堆中。
• 遍历结束后，从堆中依次取出数字（堆会自动保持最大值优先）。

示例

java
 代码解读
复制代码
public void testPriorityQueue() {
    int[] arr = {10, 15, 3, 7, 20, 11};

    //定义降序优先队列(大顶堆)
    PriorityQueue maxHeap = new PriorityQueue<>(Collections.reverseOrder());
    for (int n : arr) {
        if(isSpecial(n)) {
            maxHeap.offer(n);
        }
    }

    //查看结果
    while (!maxHeap.isEmpty()) {
        System.out.print(maxHeap.poll() + " ");
    }
    //输出结果: 20 15 11 10 7 3
}

public boolean isSpecial(int n) {
    return true;
}

优势

时间复杂度:

• 遍历数组: O(N)
• 插入堆: O(logk) 每次插入操作，k为堆的大小
• 总复杂度: O(Nlogk) 其中 N 是特殊数字的数目

空间复杂度:

• 堆的空间: O(k)，只存储特殊数字

方法 02 - 借助红黑树TreeSet

前提：如果不存在重复的 "特殊数字"

步骤

1. 使用 TreeSet 并指定降序比较器。
2. 遍历时将所有"特殊数字"加入 TreeSet。
3. 遍历结束后，直接输出 TreeSet 的内容（已按从大到小排序）。

示例

java
 代码解读
复制代码
    public void testTreeSet() {
        int[] nums = {10, 15, 3, 7, 20, 11}; // 示例输入
        TreeSet specialNumbers = new TreeSet<>(Collections.reverseOrder());

        // 遍历并将特殊数字加入 TreeSet
        for (int num : nums) {
            if (isSpecial(num)) {
                specialNumbers.add(num);
            }
        }

        System.out.println(specialNumbers);
        // 输出结果: [20, 15, 11, 10, 7, 3] 
    }

    public boolean isSpecial(int n) {
        return true;
    }

优势

TreeSet 是天然有序的，省去了排序操作

时间复杂度:

• 遍历数组：O(n)
• 插入 TreeSet：O(log k)（每次插入操作，k 是特殊数字的数量）。
• 总复杂度：O(n log k)。

空间复杂度:

• 堆的空间: O(k)，只存储特殊数字

方法 03 - 借助 ArrayList 和 Collections 工具集

步骤

• 遍历时将所有"特殊数字"存入 ArrayList
• 遍历结束后对 ArrayList 进行降序排序

示例

java
 代码解读
复制代码
    public boolean isSpecial(int n) {
        return true;
    }

    @Test
    public void testListAndCollections() {
        int[] nums = {10, 15, 3, 7, 20, 11}; // 示例输入
        List specialNumbers = new ArrayList<>();

        // 遍历并将特殊数字加入列表
        for (int num : nums) {
            if (isSpecial(num)) { // 假设 isSpecial() 是判断"特殊数字"的方法
                specialNumbers.add(num);
            }
        }

        // 对列表进行降序排序
        Collections.sort(specialNumbers, Collections.reverseOrder());

        System.out.println(specialNumbers);
        //输出结果: [20, 15, 11, 10, 7, 3]
    }

优势

时间复杂度：

• 遍历数组：O(n)
• 排序列表：O(k log k)，其中 k 是特殊数字的数量。
• 总复杂度：O(n + k log k)。

空间复杂度：

• ArrayList 的空间：O(k)，存储所有特殊数字。

小结

优选方法： PriorityQueue 或 TreeSet

• 如果需要在遍历过程中保持有序，PriorityQueue 和 TreeSet 是效率最高的选择。
• PriorityQueue 更节省内存，适合需要动态插入大量数据的场景。
• TreeSet 更简洁易用，同时支持去重。

次选方法： ArrayList

• 如果数据量较小，直接用 ArrayList 并在遍历后排序是最简单的实现方式。

补充 - Collections.reverseOrder()

以上代码在构建从大到小排序数据结构中都传入了 Collections.reverseOrder()

源码

java
 代码解读
复制代码
    public static  Comparator reverseOrder() {
        return (Comparator) ReverseComparator.REVERSE_ORDER;
    }

• 返回一个比较器，该比较器将自然排序的反面强加给对象集合
• 实现可比接口。（自然排序是由对象自己的compareTo方法。）
• 比如如果传入一个数组，数组内元素为 String
• 则: Arrays.sort(a, Collections.reverseOrder());
• 按 reverse-lexicographic（字母）顺序排序数组
• 如果传入一个数组，组内元素为 Integer 则按照元素从大到小顺序排序

其中的 REVERSE_ORDER 常量

为 ReverseComparator 实例

• 实现了 Comparator 和 Serializable 接口

java
 代码解读
复制代码
    private static class ReverseComparator
        implements Comparator>, Serializable {	//实现 Comparator 和 Serializable 接口

        private static final long serialVersionUID = 7207038068494060240L;

        //静态常量: REVERSE_ORDER 为 ReverseComparator 实例
        static final ReverseComparator REVERSE_ORDER
            = new ReverseComparator();

        //实现 compare 方法，按照从大到小顺序
        public int compare(Comparable