Daily LeetCode – day0006 1403. Minimum Subsequence in Non-Increasing Order

// 1403. Minimum Subsequence in Non-Increasing Order
class Solution {
    public List<Integer> minSubsequence(int[] nums) {
        int[] buckets = new int[101];
        int sum = 0;
        for (int num : nums) {
            ++buckets[num];
            sum += num;
        }
        int target = sum / 2 + 1;
        sum = 0;
        int i = 100;
        List<Integer> ans = new ArrayList<>();
        while (sum < target) {
            if (buckets[i] != 0) {
                --buckets[i];
                ans.add(i);
                sum += i;
            } else {
                --i;
            }
        }
        return ans;
    }
}
学习笔记:
这道题比去年七夕节的情侣牵手要无聊太多了。
这是一道排序算法和贪心算法的题目。
不过我也探索了很多,Collections.sort()其实会调用Arrays.sort()。Arrays.sort()会根据不同情况选择三种排序,如果是基本类型,则会选择快速排序DualPrivotQuicksort.sort(),如果是引用类型使用的是蒂姆排序TimSort.sort(),除非用户请求的是使用LegacyMergeSort才会用祖传的归并排序Arrays.legacyMergeSort()。Tim排序发明人是Tim Peters,也是Python之禅的作者。有机会一定要研究研究。
这道题用上面这些都不是最佳,都是3ms,而如果用了桶排序,就可以到1ms打败100%的用户。


关于樊轶群

一个善良的理想主义者。
此条目发表在每日LeetCode分类目录。将固定链接加入收藏夹。

发表回复

您的电子邮箱地址不会被公开。