1
class Solution {
2
  public int[] sortEvenOdd(int[] nums) {
3
    int[] even = new int[101];
4
    int[] odd = new int[101];
5
    int length = nums.length;
6
    for (int i = 0; i < length; ++i) {
7
      if (i % 2 == 0) {
8
        even[nums[i]]++;
9
      } else {
10
        odd[nums[i]]++;
11
      }
12
    }
13
    int e = 0;
14
    int o = 100;
15
    for (int i = 0; i < length; ++i) {
16
      if (i % 2 == 0) {
17
        // check even
18
        while (even[e] == 0) {
19
          ++e;
20
        }
21
        nums[i] = e;
22
        even[e]--;
23
      } else {
24
        while (odd[o] == 0) {
25
          --o;
26
        }
27
        nums[i] = o;
28
        odd[o]--;
29
      }
30
    }
31
    return nums;
32
  }
33
}