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

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)。

参考代码2

这道题还有一种更加巧妙的O(n)的解法。

根据题目要求nums[0] <= nums[1] >= nums[2] <= nums[3]….,可以总结出摆动排序后的数列具有以下规律:

  • 当i为奇数时,nums[i] >= nums[i – 1]
  • 当i为偶数时,nums[i] <= nums[i – 1]

那么我们只要遍历数组中每个位置数字,根据其奇偶性,如果不符合上述规律,就把该位置的数字和前面的数交换位置就行了。

相关题目

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

发表评论

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