class Solution {
public:
void wiggleSort(vector<int>& nums) {
}
};
324. 摆动排序 II
给你一个整数数组 nums，将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]... 的顺序。
你可以假设所有输入数组都可以得到满足题目要求的结果。
示例 1：
输入：nums = [1,5,1,1,6,4] 输出：[1,6,1,5,1,4] 解释：[1,4,1,5,1,6] 同样是符合题目要求的结果，可以被判题程序接受。
示例 2：
输入：nums = [1,3,2,2,3,1] 输出：[2,3,1,3,1,2]
提示：
1 <= nums.length <= 5 * 1040 <= nums[i] <= 5000nums ，总能产生满足题目要求的结果
进阶：你能用 O(n) 时间复杂度和 / 或原地 O(1) 额外空间来实现吗？
原站题解
golang 解法, 执行用时: 16 ms, 内存消耗: 6.2 MB, 提交时间: 2023-04-17 16:43:13
func wiggleSort(nums []int) {
n := len(nums)
arr := append([]int{}, nums...)
sort.Ints(arr)
x := (n + 1) / 2
for i, j, k := 0, x-1, n-1; i < n; i += 2 {
nums[i] = arr[j]
if i+1 < n {
nums[i+1] = arr[k]
}
j--
k--
}
}
javascript 解法, 执行用时: 112 ms, 内存消耗: 45.7 MB, 提交时间: 2023-04-17 16:42:59
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
var wiggleSort = function(nums) {
const arr = nums.slice();
arr.sort((a, b) => a - b);
const n = nums.length;
const x = Math.floor((n + 1) / 2);
for (let i = 0, j = x - 1, k = n - 1; i < n; i += 2, j--, k--) {
nums[i] = arr[j];
if (i + 1 < n) {
nums[i + 1] = arr[k];
}
}
};
java 解法, 执行用时: 4 ms, 内存消耗: 45.4 MB, 提交时间: 2023-04-17 16:42:47
class Solution {
public void wiggleSort(int[] nums) {
int[] arr = nums.clone();
Arrays.sort(arr);
int n = nums.length;
int x = (n + 1) / 2;
for (int i = 0, j = x - 1, k = n - 1; i < n; i += 2, j--, k--) {
nums[i] = arr[j];
if (i + 1 < n) {
nums[i + 1] = arr[k];
}
}
}
}
python3 解法, 执行用时: 52 ms, 内存消耗: 16.5 MB, 提交时间: 2023-04-17 16:42:32
class Solution:
def wiggleSort(self, nums: List[int]) -> None:
n = len(nums)
arr = sorted(nums)
x = (n + 1) // 2
j, k = x - 1, n - 1
for i in range(0, n, 2):
nums[i] = arr[j]
if i + 1 < n:
nums[i + 1] = arr[k]
j -= 1
k -= 1