LeetCode 324. Wiggle Sort II
問題
数字配列をi < j < kのときnums[i] < nums[j] > nums[k]となるように並び替えてください。
例：
Input: nums = [1,5,1,1,6,4]
Output: [1,6,1,5,1,4]
Explanation: [1,4,1,5,1,6] is also accepted.
解説
元の配列が[6,13,5,4,5,2]とする。中央値を取ったあとこのnumsは部分的にソートされている。最初の半分は中央値と同じかそれより大きく、後ろの半分は中央値と同じかそれより小さい。
13 6 5 5 4 2
M
下のリンクで紹介されているように、次の手順に従う（wiggle sort）。
- 中央値より小さい要素を後ろから偶数番目に配置する
- 中央値より大きい要素を前から奇数番目に配置する
- 中央値は残りの場所に配置する
Index : 0 1 2 3 4 5
Small half: M S S
Large half: L L M
Mは中央値。この例では[13,6,5]を1,3,5に入れて[5,4,2]を0,2,4に入れる。
Color sortを組み込んだ(1 + 2*index) % (n | 1)でこの操作ができる。中央値（この場合は5）を選んだ後、以下の処理を繰り返す。（nはnums.length）
Mapped_idx[Left]は次の中央値より小さい値が挿入される場所を示している。
Mapped_idx[Right]は次の中央値より大きい値が挿入される場所を示している。
Step 1:
Original idx: 0 1 2 3 4 5
Mapped idx: 1 3 5 0 2 4
Array: 13 6 5 5 4 2
Left
i
Right
nums[Mapped_idx[i]] = nums[i] = 6 > 5なので最初の奇数の位置である１に６を入れて良い。iとLeftに１増やす。
Step 2:
Original idx: 0 1 2 3 4 5
Mapped idx: 1 3 5 0 2 4
Array: 13 6 5 5 4 2
Left
i
Right
nums[3] = 5 = 5なのでインデックス３に６を入れて良い。iを１増やす。
Step 3:
Original idx: 0 1 2 3 4 5
Mapped idx: 1 3 5 0 2 4
Array: 13 6 5 5 4 2
Left
i
Right
nums[5] = 2 < 5なので偶数インデックス４（Right）に入れる。nums[Mapped_idx[i]]とnums[Mapped_idx[Right]]を入れ替える。
Step 4:
Original idx: 0 1 2 3 4 5
Mapped idx: 1 3 5 0 2 4
Array: 13 6 5 5 2 4
Left
i
Right
nums[5] = 4 < 5なので偶数インデックスのうち最後から２番目に入れる。nums[5]とnums[2]を入れ替え、Rightを１減らす。
Step 5:
Original idx: 0 1 2 3 4 5
Mapped idx: 1 3 5 0 2 4
Array: 13 6 4 5 2 5
Left
i
Right
nums[5] = 5 < 5なのでここでOK。iを１増やす。
Step 6:
Original idx: 0 1 2 3 4 5
Mapped idx: 1 3 5 0 2 4
Array: 13 6 4 5 2 5
Left
i
Right
nums[0] = 13 > 5なので奇数インデックスのうちの次のインデックス（３）に入れる。nums[0]とnums[3]を入れ替える。Leftとiを１増やす。
Step Final:
Original idx: 0 1 2 3 4 5
Mapped idx: 1 3 5 0 2 4
Array: 5 6 4 13 2 5
Left
i
Right
i > Rightおわり。
完成したコードはこちら
public void wiggleSort(int[] nums) {
int median = findKthLargest(nums, (nums.length + 1) / 2);
int n = nums.length;
int left = 0, i = 0, right = n - 1;
while (i <= right) {
if (nums[newIndex(i,n)] > median) {
swap(nums, newIndex(left++,n), newIndex(i++,n));
}
else if (nums[newIndex(i,n)] < median) {
swap(nums, newIndex(right--,n), newIndex(i,n));
}
else {
i++;
}
}
}
private int newIndex(int index, int n) {
return (1 + 2*index) % (n | 1);
}
Discussion