324 Wiggle Sort II 擺動(dòng)排序 II
Description:
Given an unsorted array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]....
Example:
Example 1:
Input: nums = [1, 5, 1, 1, 6, 4]
Output: One possible answer is [1, 4, 1, 5, 1, 6].
Example 2:
Input: nums = [1, 3, 2, 2, 3, 1]
Output: One possible answer is [2, 3, 1, 3, 1, 2].
Note:
You may assume all input has valid answer.
Follow up:
Can you do it in O(n) time and/or in-place with O(1) extra space?
題目描述:
給定一個(gè)無(wú)序的數(shù)組 nums，將它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]... 的順序瘩将。
示例 :
示例 1:
輸入: nums = [1, 5, 1, 1, 6, 4]
輸出: 一個(gè)可能的答案是 [1, 4, 1, 5, 1, 6]
示例 2:
輸入: nums = [1, 3, 2, 2, 3, 1]
輸出: 一個(gè)可能的答案是 [2, 3, 1, 3, 1, 2]
說明:
你可以假設(shè)所有輸入都會(huì)得到有效的結(jié)果。
進(jìn)階：
你能用 O(n) 時(shí)間復(fù)雜度和 / 或原地 O(1) 額外空間來實(shí)現(xiàn)嗎？
思路:
- 排序再交叉插入原數(shù)組
比如 [1, 2, 3], [4, 5], 插入之后就可以得到 [1, 4, 2, 5, 3]
時(shí)間復(fù)雜度O(nlgn), 空間復(fù)雜度O(1) - 利用快速排序的思想, 找到數(shù)組的中位數(shù)
然后將數(shù)組按中位數(shù)分開, 那么中位數(shù)左邊都比中位數(shù)小, 右邊都比中位數(shù)大
然后將中位數(shù)兩邊的數(shù)組反向, 再依次插入就能得到擺動(dòng)數(shù)組
比如 [1, 2, 5, 5, 5, 5, 6, 7] -> [5, 5, 2, 1], [7, 6, 5, 5] -> [5, 7, 5, 6, 2, 5, 1, 5]
時(shí)間復(fù)雜度O(nlgn), 空間復(fù)雜度O(1)
代碼:
C++:
class Solution
{
public:
void wiggleSort(vector<int>& nums)
{
nth_element(nums.begin(), nums.begin() + (nums.size() >> 1), nums.end());
int n = nums.size(), mid = nums[nums.size() >> 1], i = 0, j = 0, k = nums.size() - 1;
#define f(i) nums[(((i) << 1) + 1) % (n | 1)]
while (j <= k)
{
if (f(j) > mid)
{
swap(f(i), f(j));
++i;
++j;
}
else if (f(j) < mid)
{
swap(f(j), f(k));
--k;
}
else ++j;
}
}
};
Java:
class Solution {
private void swap(int[] nums, int p, int q) {
int temp = nums[p];
nums[p] = nums[q];
nums[q] = temp;
}
private int getIndex(int n, int i) {
return i <= (n - 1) / 2 ? i * 2 : (i - (n + 1) / 2) * 2 + 1;
}
private int getKth(int[] nums, int k) {
int n = nums.length, start = 0, end = n - 1;
while (true) {
int pivot = nums[getIndex(n, end)], p = start, q = p;
for (int i = start; i < end; i++)
if (nums[getIndex(n, i)] <= pivot) {
swap(nums, getIndex(n, q++), getIndex(n, i));
if (nums[getIndex(n, q - 1)] < pivot) swap(nums, getIndex(n, p++), getIndex(n, q - 1));
}
swap(nums, getIndex(n, q++), getIndex(n, end));
if (k < p - start) end = p - 1;
else if (k < q - start) return pivot;
else {
k -= q - start;
start = q;
}
}
}
public void wiggleSort(int[] nums) {
int n = nums.length, mid = (n - 1) / 2;
getKth(nums, mid);
for (int p = 0, q = mid; p < q; p++, q--) swap(nums, getIndex(n, p), getIndex(n, q));
for (int p = mid + 1, q = n - 1; p < q; p++, q--) swap(nums, getIndex(n, p), getIndex(n, q));
}
}
Python:
class Solution:
def wiggleSort(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
nums[0::2], nums[1::2] = sorted(nums)[:len(nums) - (len(nums) >> 1)][::-1], sorted(nums)[len(nums) - (len(nums) >> 1):][::-1]
