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%的用户。