LintCode 508. Wiggle Sort 原创Java参考解答
问题描述
http://www.lintcode.com/en/problem/wiggle-sort/
Given an unsorted array nums, reorder it in-place such that
nums[0] <= nums[1] >= nums[2] <= nums[3]....
Notice
Please complete the problem in-place.
Example
Given nums = [3, 5, 2, 1, 6, 4], one possible answer is [1, 6, 2, 5, 3, 4].
解题思路
题目是需要把数组按照第一个数 <= 下一个数，下一个数 >= 再下一个数…依次不断按 <= 和 >= 交错的顺序进行摆动排序。
对于这种另类排序的题，考察你的观察力和归纳能力。
提一些问题帮助帮助自己思考：
- 什么的数组符合摆动排序要求？举例子
- 摆动排序数组有什么特点？ 观察相邻位置数字的关系，观察奇偶位置数字的大小特点……
- 怎么调整一个数组使它成为摆动数组？需要先排序吗？
参考代码1
首先，这道题有一种容易想到的解法：对数组先排序，然后从第三个数开始每两个数做一次位置交换。把第三个数和第二个数调换个位置，第五个数和第四个数调换个位置…..以此类推直至数组末尾。这样就完成摆动排序了。算法复杂度是快速排序的复杂度O(NlogN)。
public class Solution {
/**
* @param nums a list of integer
* @return void
*/
public void wiggleSort(int[] nums) {
Arrays.sort(nums);
for (int i = 2; i < nums.length; i += 2) {
swap(nums, i - 1, i);
}
}
public void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
参考代码2
这道题还有一种更加巧妙的O(n)的解法。
根据题目要求nums[0] <= nums[1] >= nums[2] <= nums[3]….，可以总结出摆动排序后的数列具有以下规律：
- 当i为奇数时，nums[i] >= nums[i – 1]
- 当i为偶数时，nums[i] <= nums[i – 1]
那么我们只要遍历数组中每个位置数字，根据其奇偶性，如果不符合上述规律，就把该位置的数字和前面的数交换位置就行了。
public class Solution {
/**
* @param nums a list of integer
* @return void
*/
public void wiggleSort(int[] nums) {
for (int i = 1; i < nums.length; i++) {
if ((i % 2 == 1 && (nums[i] < nums[i - 1])) ||
(i % 2 == 0 && (nums[i] > nums[i - 1]))) {
swap(nums, i - 1, i);
}
}
}
public void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}