[leetcode] 324. Wiggle Sort II

[leetcode] 324. Wiggle Sort II

Description

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

Example 1:

Input:

nums = [1, 5, 1, 1, 6, 4]

Output:

One possible answer is [1, 4, 1, 5, 1, 6].

Example 2:

Input:

nums = [1, 3, 2, 2, 3, 1]

Output:

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?

分析

题目的意思是：给定一个无序数组，把该数组排序成摆动数组，满足nums[0] < nums[1] > nums[2] < nums[3]…。

STL中的nth_element()方法的使用 通过调用nth_element(start, start+n, end) 方法可以使第n大元素处于第n位置（从0开始,其位置是下标为 n的元素），并且比这个元素小的元素都排在这个元素之前，比这个元素大的元素都排在这个元素之后，但不能保证他们是有序的。是一个数组的题目，需要读者手工模拟一下计算过程。先把mid位置的值求出来，然后把小于该值的元素放在前面，大于该元素的值放在后面，然后遍历，然后前后位置通过交换得到摆动数组。这道题有些地方我也不是很懂，有兴趣的可以交流一下。

代码

class Solution {public: void wiggleSort(vector& nums) { int n=nums.size(); auto midptr=nums.begin()+n/2; nth_element(nums.begin(),midptr,nums.end()); int mid=*midptr; // Index-rewiring. #define A(i) nums[(1+2*(i)) % (n|1)] int i=0; int j=0; int k=n-1; while(j<=k){ if(A(j)>mid){ swap(A(i++),A(j++)); }else if(A(j)

参考文献

​​324. Wiggle Sort II​​​​STL中的nth_element()方法的使用​​​​[LeetCode] Wiggle Sort II 摆动排序之二​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。