leetcode 324. Wiggle Sort II

太过爱你忘了你带给我的痛 2022-08-20 14:26 156阅读 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?

class Solution {
    public:
    	void wiggleSort(vector<int>& nums) {
    		if(nums.empty())
    			return;
    
    		vector<int>aa=nums;
    		sort(aa.begin(),aa.end());
    		if(nums.size()%2!=0)
    			for(int i=0;i<aa.size();)
    			{
    				nums[i]=aa[i/2];
    				if(i+1<aa.size())
    					nums[i+1]=aa[nums.size()/2+i/2+1];
    				i+=2;
    			}
    		else
    		{
    			for(int i=0;i<aa.size();)
    			{
    				nums[i]=aa[i/2];
    				if(i+1<aa.size())
    				{
    					nums[i+1]=aa[nums.size()/2+i/2];
    				}
    				i+=2;
    			}
    		}
    		for(int i=2;i<nums.size()-1;)
    		{
    			if(nums[i-1]<=nums[i])
    			{
    				int tp=nums[i+1];
    				nums[i+1]=nums[i-1];
    				nums[i-1]=tp;
    				i=2;
    			}
    			else if(nums[i+1]<=nums[i])
    			{
    				int tp=nums[i];
    				nums[i]=nums[i-2];
    				nums[i-2]=tp;
    				i=2;
    			}
    			else
    				i+=2;
    		}
    	}
    };

accepted

发表评论取消回复

表情：

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

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

相关阅读

相关 LeetCode_排序_中等_324.摆动排序 II

目录 1.题目 2.思路 3.代码实现（Java） 1.题目给你一个整数数组 nums，将它重新排列成 nums\[0\] < nums\[1

柔情只为你懂/ 2023年10月06日 18:53/ 0 赞/ 16 阅读

相关 324. 摆动排序 II（JS实现）

1 题目 > 给定一个无序的数组 nums，将它重新排列成 nums\[0\] < nums\[1\] > nums\[2\] < nums\[3\]… 的顺序。 >

太过爱你忘了你带给我的痛/ 2022年11月28日 00:21/ 0 赞/ 254 阅读

相关 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. 摆动排序 II（DAY 163）---- LeetCode 精选 TOP 面试题

文章目录原题题目代码实现（首刷自解主要是思路） -------------------- 原题题目 --------------

左手的ㄟ右手/ 2022年09月10日 07:12/ 0 赞/ 117 阅读

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

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

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