Wiggle Sort II

约定不等于承诺〃 2021-10-24 06:22 286阅读 0赞

Given an unsorted array `nums`, reorder it such that `nums[0] < nums[1] > nums[2] < nums[3]...`.

Example:  
(1) Given `nums = [1, 5, 1, 1, 6, 4]`, one possible answer is `[1, 4, 1, 5, 1, 6]`.   
(2) Given `nums = [1, 3, 2, 2, 3, 1]`, 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?

Analyse: space: O(n), time: O(nlogn).

Runtime: 140ms

1 class Solution {
     2 public:
     3     void wiggleSort(vector<int>& nums) {
     4         // the number with odd index should be larger than others
     5         // find the larger part of the array, then insert the smaller and larger part correspondingly
     6         vector<int> temp = nums;
     7         sort(temp.begin(), temp.end());
     8         
     9         int n = nums.size(), k = (n + 1) / 2;
    10         for(int i = 0; i < nums.size(); i++)
    11             nums[i] = i & 1 ? temp[--n] : temp[--k];
    12     }
    13 };

转载于:https://www.cnblogs.com/amazingzoe/p/5743223.html

发表评论取消回复

表情：

评论列表（有 0 条评论，286人围观）

还没有评论，来说两句吧...

相关阅读

相关 leetcode 324. Wiggle Sort II

[https://leetcode.com/problems/wiggle-sort-ii/][https_leetcode.com_problems_wiggle-sort-

港控/mmm°/ 2023年07月09日 04:29/ 0 赞/ 48 阅读

相关 LeetCode Top Interview Questions 324. Wiggle Sort II (Java版; Medium)

[welcome to my blog][] LeetCode Top Interview Questions 324. Wiggle Sort II (Java版;

曾经终败给现在/ 2023年07月02日 08:28/ 0 赞/ 51 阅读

相关 324. Wiggle Sort II | 324. 摆动排序 II（降序穿插）

题目 [https://leetcode.com/problems/wiggle-sort-ii/submissions/][https_leetcode.com_pro

ゞ浴缸里的玫瑰/ 2022年10月20日 00:55/ 0 赞/ 190 阅读

相关 leetcode 324. Wiggle Sort II

Given an unsorted array nums, reorder it such that nums\[0\] < nums\[1\] > nums\[2\] < n

太过爱你忘了你带给我的痛/ 2022年08月20日 14:26/ 0 赞/ 215 阅读

相关 leetcode 324. Wiggle Sort II 摇摆排序

Given an unsorted array nums, reorder it such that nums\[0\] < nums\[1\] > nums\[2\] < n

ゝ一世哀愁。/ 2022年06月07日 01:09/ 0 赞/ 187 阅读

相关 922. Sort Array By Parity II

Given an array `A` of non-negative integers, half of the integers in A are odd, and half

朱雀/ 2022年04月25日 03:28/ 0 赞/ 186 阅读

相关 376. Wiggle Subsequence

A sequence of numbers is called a wiggle sequence if the differences between successive

缺乏、安全感/ 2022年04月23日 09:04/ 0 赞/ 221 阅读

相关 Lintcode: Sort Colors II 解题报告

[Sort Colors II ][Sort Colors II] 原题链接： [http://lintcode.com/zh-cn/problem/sort-color

柔光的暖阳◎/ 2022年04月22日 15:26/ 0 赞/ 266 阅读

相关 324. Wiggle Sort II

324. Wiggle Sort II \---摆动排序问题 Given an unsorted array `nums`, reorder it such that `n

r囧r小猫/ 2021年12月22日 20:59/ 0 赞/ 218 阅读

相关 Wiggle Sort II

Given an unsorted array `nums`, reorder it such that `nums[0] < nums[1] > nums[2] < nums

约定不等于承诺〃/ 2021年10月24日 06:22/ 0 赞/ 287 阅读