题解 | #牛牛的桶排序#

思路

桶排。观察到数据范围是 ，所以设置一个偏移量 offset 即可。

最后空间复杂度为 ，时间复杂度为 。

参考代码

import java.util.*;


public class Solution {
    int[] bucket = new int[100000 + 10];
    int offset = 5 * 10000;
   
    public int[] bucketSort (int[] nums) {
        List<Integer> list = new ArrayList<>();

        for (int num : nums) {
            bucket[num + offset] ++;
        }

        for (int i = 0; i <= 100000; i++) {
            if (bucket[i] == 0) continue;
            while (bucket[i] > 0) {
                list.add(i - offset);
                bucket[i] --;
            }
        }
        //System.out.println(list.size());
        return list.stream().mapToInt(i -> i).toArray();
    }
}