LeetCode 324. 摆动排序 II

324. 摆动排序 II

【计数排序】因为nums[i]的范围在5000内，所以可以考虑计数排序，虽然需要O(m)的空间复杂度，但是可以保证O(n)的时间复杂度。具体做法就是，先统计每个出现的次数，从前往后先把奇数位置放上最大的一半元素，然后从头到尾再把偶数位置放上次大的元素。

class Solution {

    // 计数排序 10:46 10:49

    public void wiggleSort(int[] nums) {
        int[] cnt = new int[5001];
        for (var x: nums) {
            cnt[x]++;
        } 
        int j = 5000, n = nums.length;
        for (var i = 1; i < n; i += 2) {
            while (cnt[j] == 0) {
                j--;
            }
            nums[i] = j;
            cnt[j]--;
        }
        for (var i = 0; i < n; i += 2) {
            while (cnt[j] == 0) {
                j--;
            }
            nums[i] = j;
            cnt[j]--;
        }
    }
}