Java实现电商每日特色商品获取方案是否最优及时间复杂度咨询

时间复杂度 #

原实现的时间复杂度最坏为O(n log n)，平均场景下为O(n + m log m)：

• n为输入商品列表的总长度，统计商品销量的遍历过程时间复杂度为O(n)
• m为销量等于最高销量的商品数量，原实现对这部分商品做排序的时间复杂度为O(m log m)
• 最坏情况为所有商品销量相同，此时m等于不同商品的总数量k，极端场景下k=n，排序步骤的时间复杂度退化为O(n log n)，成为整体性能瓶颈
• 其余查找最高销量、筛选高销量商品的步骤时间复杂度均为O(k)（k≤n），不会成为瓶颈

是否为最优方案 #

原实现不是最优方案，可以优化到稳定的*O(n)*时间复杂度：
不需要对所有最高销量的商品做全量排序，你可以在遍历销量映射的过程中，直接维护「销量等于最高值、且字典序最大」的商品，省去排序的开销。
优化后的代码示例：

public static String getFeaturedProduct(List<String> items) {
    Map<String, Integer> countMap = new HashMap<>();
    // 统计商品销量
    for (String item : items) {
        countMap.merge(item, 1, Integer::sum);
    }
    int maxCount = Collections.max(countMap.values());
    String featuredProd = "";
    // 一次遍历直接得到结果，无需排序
    for (Map.Entry<String, Integer> entry : countMap.entrySet()) {
        if (entry.getValue() == maxCount && entry.getKey().compareTo(featuredProd) > 0) {
            featuredProd = entry.getKey();
        }
    }
    System.out.println("the featured item is : " + featuredProd);
    return featuredProd;
}

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