Hard 507. Wiggle Sort II

way 1: 排序, 然后交错, 从大到小排放. O(n log n) time

A.sort()
res = [None] * n
res[0::2] = A[0:mid][::-1]
res[1::2] = A[mid:][::-1]

way 2: 找到中位数, quick select, O(n) time

找到中位数 A[mid], 相当于排序后的 mid = n//2,
- 全部填满中位数,解决中位数可能重复的问题.
小数从后往前摆放, 偶数, 指针 r = n - 2 (倒数第二个), 奇数: 指针 r = n - 1 (倒数第一个).
 - 奇数个, i.e. 1 2 1, 小的在最后边.
 - 偶数个, i.e. 1 2 1 2, 小的在倒数第二个, 大的在最后.
大数从前往后摆放, 指针从 l = 1 开始. - 从哪里开始, 太难了, 只能靠记忆.
- i.e. 1 8 2 7, 大树从第二个开始, l = 1.

```
2 3 5 5 7 8
5 7 2 8 3 5
偶数个, 7: l = 1, 3: r = n - 2

2 3 5 5 5 7 8
5 8 5 7 3 5 2
奇数个, 8: l = 1, 2: r = n - 1.
```

# way 1: O(n log n)

class Solution:
    def wiggleSort(self, A):
        if not A or len(A) < 2:
            return
        # init
        A.sort()
        n = len(A)
        res = [None] * n
        mid_v = A[n//2]
        if n & 1 == 1:
            mid = n//2 + 1
        else:
            mid = n//2
        res[0::2] = A[0:mid][::-1]
        res[1::2] = A[mid:][::-1]
        # print(res)
        A[:] = res

A = [1, 3, 2, 2, 3, 1]
# Output: [2, 3, 1, 3, 1, 2]
;

# way 2: O(n)

class Solution:
    def wiggleSort(self, A):
        if not A or len(A) < 2:
            return
        # init
        A.sort()
        n = len(A)
        mid_v = A[n//2] # can do quick select, O(n)
        res = [mid_v] * n
        l = 1
        if n & 1 == 1: # 奇数个, i.e. 1 2 1, 小的在最后边.
            r = n - 1
        else:
            r = n - 2

        for v in A:
            if v > mid_v:
                res[l] = v
                l += 2
            elif v < mid_v:
                res[r] = v
                r -= 2

        A[:] = res