Wiggle Sort II

约定不等于承诺〃 2021-10-24 06:22 224阅读 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 条评论，224人围观）

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

相关阅读

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

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

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

相关 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 赞/ 157 阅读

相关 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 赞/ 118 阅读

相关 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 赞/ 117 阅读

相关 376. Wiggle Subsequence

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

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

相关 Lintcode: Sort Colors II 解题报告

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

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

相关【Leetcode】376. Wiggle Subsequence

1. Wiggle Subsequence A sequence of numbers is called a wiggle sequence if the differe

忘是亡心i/ 2022年04月16日 04:18/ 0 赞/ 159 阅读

相关 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 赞/ 150 阅读

相关 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 赞/ 225 阅读

相关 leetcode--Search in Rotated Sorted Array II

Follow up for "Search in Rotated Sorted Array": What if duplicates are allowed? Would

Bertha 。/ 2021年10月16日 01:12/ 0 赞/ 230 阅读