LeetCode 280. Wiggle Sort （摆动排序）$

Given an unsorted array nums, reorder it in-place such that nums[0] <= nums[1] >= nums[2] <= nums[3]....

For example, given nums = [3, 5, 2, 1, 6, 4], one possible answer is [1, 6, 2, 5, 3, 4].

题目标签：Array, Sort

　　题目给了我们一个nums array，让我们wiggle sort。

　　wiggle sort 特性：所有index 是odd 的数字大于等于两边数字。

　　我们可以从另一个角度理解：所有even index 的数字要小于下一个数字；所有odd index 的数字要大于等于下一个数字。

　　这样就可以遍历nums，根据奇数偶数来检查每一对数字，如果不符合要求的，swap 它们。

Java Solution:

Runtime beats 60.02%

完成日期：09/10/2017

关键词：Array

关键点：遍历检查每一对数字，不符合要求就对换

 1 class Solution 
 2 {
 3     public void wiggleSort(int[] nums) 
 4     {
 5         for(int i=0; i<nums.length; i++)
 6         {
 7             // for even index
 8             if(i % 2 == 0)
 9             {   
10                 // if even index number >  next one, swap them
11                 if(i+1 < nums.length && nums[i] > nums[i+1])
12                 {
13                     int temp = nums[i];
14                     nums[i] = nums[i+1];
15                     nums[i+1] = temp;
16                 }
17             }
18             else // for odd index
19             {
20                 // if odd index number < next one, swap them
21                 if(i+1 < nums.length && nums[i] < nums[i+1])
22                 {
23                     int temp = nums[i];
24                     nums[i] = nums[i+1];
25                     nums[i+1] = temp;
26                 }
27             }
28         }
29     }
30 }

参考资料：N/A

LeetCode 算法题目列表 - LeetCode Algorithms Questions List