求最坏时间复杂度Θ(n)的特殊频次数组排序Java算法

核心思路 #

利用题目中元素出现次数的特性（最多的元素占当前数组长度的一半以上），通过摩尔投票法快速定位出现次数最多的元素，逐步分离出所有不同元素；再对少量不同元素排序（数量为log₂n，时间可忽略），最后按顺序填充结果数组。

步骤分解 #

1. 收集所有不同元素及其出现次数

   • 对当前数组，用摩尔投票法找出出现次数最多的元素（因该元素占比超过数组长度的1/2，摩尔投票法可线性时间找到）。
   • 统计该元素的出现次数，并分离出数组中剩余元素（剩余数组仍符合题目中出现次数的比例规则）。
   • 重复上述过程，直到数组为空。

2. 排序不同元素

   • 收集到的不同元素数量为log₂n（因n=2^k，k为整数），对这少量元素排序的时间可忽略不计。

3. 生成排序后的数组

   • 按照排序后的元素顺序，依次将每个元素重复其出现次数填充到结果数组中。

Java 实现代码 #

import java.util.*;

public class SpecialSort {

    // 摩尔投票法找出现次数最多的元素（题目保证存在）
    private static int findMajorityElement(int[] arr) {
        int candidate = arr[0];
        int count = 1;
        for (int i = 1; i < arr.length; i++) {
            if (count == 0) {
                candidate = arr[i];
                count = 1;
            } else if (arr[i] == candidate) {
                count++;
            } else {
                count--;
            }
        }
        return candidate;
    }

    // 统计元素出现次数，并分离出剩余元素
    private static Pair<Integer, int[]> extractElement(int[] arr, int target) {
        int count = 0;
        List<Integer> restList = new ArrayList<>();
        for (int num : arr) {
            if (num == target) {
                count++;
            } else {
                restList.add(num);
            }
        }
        int[] restArr = restList.stream().mapToInt(Integer::intValue).toArray();
        return new Pair<>(count, restArr);
    }

    public static int[] specialSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return new int[0];
        }

        // 收集所有元素及其出现次数
        List<Pair<Integer, Integer>> elementCounts = new ArrayList<>();
        int[] currentArr = Arrays.copyOf(arr, arr.length);
        while (currentArr.length > 0) {
            int major = findMajorityElement(currentArr);
            Pair<Integer, int[]> result = extractElement(currentArr, major);
            elementCounts.add(new Pair<>(major, result.getKey()));
            currentArr = result.getValue();
        }

        // 按元素数值排序
        elementCounts.sort(Comparator.comparingInt(Pair::getKey));

        // 生成排序后的数组
        int[] sortedArr = new int[arr.length];
        int pos = 0;
        for (Pair<Integer, Integer> pair : elementCounts) {
            int num = pair.getKey();
            int count = pair.getValue();
            Arrays.fill(sortedArr, pos, pos + count, num);
            pos += count;
        }

        return sortedArr;
    }

    public static void main(String[] args) {
        int[] input = {5, 1, 2, 5, 2, 5, 5};
        int[] output = specialSort(input);
        System.out.println(Arrays.toString(output)); // 输出 [1, 2, 2, 5, 5, 5, 5]
    }
}

时间复杂度分析 #

• 收集元素阶段：每次处理长度为m的数组，后续处理长度为m/2左右的数组，总操作次数为 (n-1) + (n/2-1) + (n/4-1) + ... + 1 = Θ(n)。
• 排序阶段：仅对log₂n个元素排序，时间为 Θ((log n)^2)，相对于Θ(n)可忽略。
• 填充数组阶段：线性遍历填充，时间为Θ(n)。
  整体时间复杂度为Θ(n)，符合要求。

为什么HashTable方法不可行 #

HashTable的插入和查询操作在最坏情况下（如哈希冲突严重）时间复杂度为Θ(n)，统计所有元素次数的总时间会达到Θ(n²)，无法满足题目要求的Θ(n)最坏时间复杂度。而本解法利用题目特有的出现次数规则，避免了哈希冲突的风险，保证了线性时间。

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