2164. Sort Even and Odd Indices Independently

sort

T : O(nlogn)

S: O(n)

class Solution {
    public int[] sortEvenOdd(int[] nums) {
        int n = nums.length;
        List<Integer> odd = new ArrayList<>();
        List<Integer> even = new ArrayList<>();
        for (int i = 0 ; i < n; i++) {
            if (i % 2 == 0) { // even, asc
                even.add(nums[i]);
            } else { // odd, desc
                odd.add(nums[i]);
            }
        }
        Collections.sort(odd, (a, b) -> b - a);
        Collections.sort(even);
        int[] res = new int[n];
        int evenIdx = 0;
        int oddIdx = 0;
        for (int i = 0 ; i < n; i++) {
            if (i % 2 == 0) { // even, asc
                res[i] = even.get(evenIdx++); // 0, 2 (i = 0)
            } else { // odd, desc
                res[i] = odd.get(oddIdx++); // 0(i = 1, 3, 5)
            }
        }
        return res;
    }
}

/*
odd -> desc
[4,1,2,3] before this step, it becomes [4,3,2,1]

even -> asc
[4,1,2,3] before this step, it becomes [2,1,4,3]
*/

bucket sort

因為這題數據很小, use bucket sort

T: O(100*n) = O(n)

S: O(202)

class Solution {
    public int[] sortEvenOdd(int[] nums) {
        int n = nums.length;
        int[] odd = new int[101]; // record count, number have duplicate number
        int[] even = new int[101]; // record count
        for (int i = 0 ; i < n; i++) {
            if (i % 2 == 0) { // even, asc
                even[nums[i]]++; 
            } else { // odd, desc
                odd[nums[i]]++;
            }
        }

        int[] res = new int[n];
        int evenIdx = 0;
        int oddIdx = 100;
        for (int i = 0; i < n; ++i) {
            if (i % 2 == 0) {
                // check even
                while (even[evenIdx] == 0) {
                    evenIdx++;
                }
                res[i] = evenIdx;
                even[evenIdx]--; // count--
            } else {
                while(odd[oddIdx] == 0) { // if there is count, pass then add data
                    oddIdx--;
                }
                res[i] = oddIdx;
                odd[oddIdx]--; // count--
            }
        }
        return res;
    }
}

/*
odd -> desc
[4,1,2,3] before this step, it becomes [4,3,2,1]

even -> asc
[4,1,2,3] before this step, it becomes [2,1,4,3]
*/a