324. Wiggle Sort II

324. Wiggle Sort II

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?

思路： 题意大致为将给定数组中的元素按形如nums[0] < nums[1] > nums[2] < nums[3]….这种样子排列，顺序没要求。 先复制当前数组，将复制的数组排序，然后以中位数为界将数组分为两部分，small part和large part。交替填入原始数组即可，这样做的原因是可以避免有值相同的数组挨在一起，以符合题目规则。 交替填入也得注意必须降序交替，否则任然有可能挨在一起。比如[4, 5, 5, 6]这一组如果升序交替填入任然是4、5、5、6，降序则为5、6、4、5。

class Solution { public void wiggleSort(int[] nums) { int[] temp = Arrays.copyOfRange(nums, 0, nums.length); Arrays.sort(temp); int large = temp.length / 2 + (temp.length % 2 == 0 ? -1 : 0); int small = temp.length - 1; for (int i = 0, j = 1; i < temp.length; i += 2, j += 2) { if(j < temp.length) nums[j] = temp[small--]; nums[i] = temp[large--]; } }}

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