🐥

LeetCode 324. Wiggle Sort II

2022/06/11に公開約3,800字

問題

数字配列を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)。

  1. 中央値より小さい要素を後ろから偶数番目に配置する
  2. 中央値より大きい要素を前から奇数番目に配置する
  3. 中央値は残りの場所に配置する
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なので最初の奇数の位置である1に6を入れて良い。iとLeftに1増やす。

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なのでインデックス3に6を入れて良い。iを1増やす。

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なので偶数インデックス4(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なので偶数インデックスのうち最後から2番目に入れる。nums[5]とnums[2]を入れ替え、Rightを1減らす。

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を1増やす。

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なので奇数インデックスのうちの次のインデックス(3)に入れる。nums[0]とnums[3]を入れ替える。Leftとiを1増やす。

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

ログインするとコメントできます