LintCode 508. Wiggle Sort 原创Java参考解答

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; 
    } 
}

相关题目

LintCode All in One 原创题目讲解汇总

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注