LeetCode 324. Swing sort II

324. Swing sort II

【 Count sorting 】 because nums[i] The scope of 5000 Inside , So you can consider counting and sorting , Although need O(m) Spatial complexity of , But it can guarantee O(n) Time complexity of . The specific method is , Count the times of each occurrence first , From front to back, put the largest half element in the odd position , Then put the even position of the last large element from beginning to end .

class Solution {

    //  Count sorting  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]--;
        }
    }
}