class Solution {
public:
void wiggleSort(vector<int>& nums) {
}
};
280. 摆动排序
给你一个的整数数组 nums, 将该数组重新排序后使 nums[0] <= nums[1] >= nums[2] <= nums[3]...
输入数组总是有一个有效的答案。
示例 1:
输入：nums = [3,5,2,1,6,4]
输出：[3,5,1,6,2,4]
解释：[1,6,2,5,3,4]也是有效的答案
示例 2:
输入：nums = [6,6,5,6,3,8] 输出：[6,6,5,6,3,8]
提示：
1 <= nums.length <= 5 * 1040 <= nums[i] <= 104输入的 nums 保证至少有一个答案。
进阶：你能在 O(n) 时间复杂度下解决这个问题吗？
原站题解
golang 解法, 执行用时: 16 ms, 内存消耗: 4.9 MB, 提交时间: 2023-10-21 20:02:27
func wiggleSort(nums []int) {
// 遍历数组，为了只遍历奇数index的数据，没采用range
for i := 1; i < len(nums); i+=2 {
// 数据量过少，直接返回
if 0 == len(nums) || 1 == len(nums){
return
}
//前一个数比当前数大，则交换
if nums[i-1] > nums[i]{
nums[i-1], nums[i] = nums[i], nums[i-1]
}
//没有最后一个数，需要对nums[i+1]保护，避免越界
if i == len(nums)-1{
break
}
//后一个数比当前数大，则交换
if nums[i+1] > nums[i]{
nums[i+1], nums[i] = nums[i], nums[i+1]
}
}
}
java 解法, 执行用时: 0 ms, 内存消耗: 44 MB, 提交时间: 2023-10-21 20:01:59
class Solution {
public void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
public void wiggleSort(int[] nums) {
for (int i = 0; i < nums.length - 1; i++) {
if (((i % 2 == 0) && nums[i] > nums[i + 1])
|| ((i % 2 == 1) && nums[i] < nums[i + 1])) {
swap(nums, i, i + 1);
}
}
}
}
java 解法, 执行用时: 3 ms, 内存消耗: 44 MB, 提交时间: 2023-10-21 20:01:45
class Solution {
public void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
public void wiggleSort(int[] nums) {
Arrays.sort(nums);
for (int i = 1; i < nums.length - 1; i += 2) {
swap(nums, i, i + 1);
}
}
}
cpp 解法, 执行用时: 8 ms, 内存消耗: 13.7 MB, 提交时间: 2023-10-21 20:01:19
class Solution {
public:
void wiggleSort(vector<int>& nums) {
int n = nums.size();
for (int i = 0; i < n - 1; i ++) {
if (i % 2 == 0) { //偶数位置(实指，从0开始)，要小于等于两侧---> 小于等于右侧
if (nums[i] > nums[i+1])
swap(nums[i], nums[i+1]);
} else { //奇数位置，要大于等于两侧---> 大于等于右侧
if (nums[i] < nums[i+1])
swap(nums[i], nums[i+1]);
}
}
}
void wiggleSort2(vector<int>& n) {
sort(n.begin(), n.end());
for (int i{1}; i < (int)n.size()-1; i += 2) {
swap(n[i], n[i+1]);
}
}
};
python3 解法, 执行用时: 52 ms, 内存消耗: 16.7 MB, 提交时间: 2023-10-21 20:00:17
class Solution:
def wiggleSort(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
n = len(nums)
for i in range(n - 1):
if i % 2 == 0:
if nums[i] > nums[i+1]:
nums[i], nums[i+1] = nums[i+1], nums[i]
else:
if nums[i] < nums[i+1]:
nums[i], nums[i+1] = nums[i+1], nums[i]