lintcode 摆动排序(Wiggle Sort) (Java)

题目

给你一个没有排序的数组，请将原数组就地重新排列满足如下性质 nums[0] <= nums[1] >= nums[2] <= nums[3]….

样例

给出数组为 nums = [3, 5, 2, 1, 6, 4] 一种输出方案为 [1, 6, 2, 5, 3, 4]

分析

1.个人分析：首先要满足nums[0] <= nums[1] >= nums[2] <= nums[3]，并参考样例，我感觉一半正序，一半倒序穿插可以满足，所以选择了选择排序，并根据要求进行穿插。这样由于两次for循环时间复杂度是O(n^2)。

代码

public class Solution { /** * @param nums a list of integer * @return void */ public void wiggleSort(int[] nums) { // Write your code here for (int i = 0; i < nums.length; i++){ int type = i%2; int max = nums[i]; int min = nums[i]; int index = i; int temp; for (int j = i; j < nums.length; j++){ if (type == 0){ if (nums[j] < min){ min = nums[j]; index = j; } }else { if (nums[j] > max){ max = nums[j]; index = j; } } } temp = nums[index]; nums[index] = nums[i]; nums[i] = temp; } } }

进一步分析

经过查资料对比学习，我发现我的方法好low

排序法 ——时间 O(NlogN) 空间 O(1) 思路：根据题目的定义，摇摆排序的方法将会很多种。我们可以先将数组排序，这时候从第3个元素开始，将第3个元素和第2个元素交换。然后再从第5个元素开始，将第5个元素和第4个元素交换，以此类推。就能满足题目要求。

public class Solution { public void wiggleSort(int[] nums) { // 先将数组排序 Arrays.sort(nums); // 将数组中一对一对交换 for(int i = 2; i < nums.length; i+=2){ int tmp = nums[i-1]; nums[i-1] = nums[i]; nums[i] = tmp; } } }

交换法 ——时间 O(N) 空间 O(1) 思路：题目对摇摆排序的定义有两部分： 如果i是奇数，nums[i] >= nums[i - 1] 如果i是偶数，nums[i] <= nums[i - 1] 所以我们只要遍历一遍数组，把不符合的情况交换一下就行了。具体来说，如果nums[i] > nums[i - 1]， 则交换以后肯定有nums[i] <= nums[i - 1]。

public class Solution { public void wiggleSort(int[] nums) { for(int i = 1; i < nums.length; i++){ // 需要交换的情况：奇数时nums[i] < nums[i - 1]或偶数时nums[i] > nums[i - 1] if((i % 2 == 1 && nums[i] < nums[i-1]) || (i % 2 == 0 && nums[i] > nums[i-1])){ int tmp = nums[i-1]; nums[i-1] = nums[i]; nums[i] = tmp; } } } }

参考地址：https://segmentfault.com/a/1190000003783283

题目地址：http://www.lintcode.com/zh-cn/problem/wiggle-sort/