Google 2016 面试题 2 摆动排序 II

题目描述给出一个整数数组nums，重新排列nums使得nums[0]nums[2]...

题目描述 

给出一个整数数组nums，重新排列nums使得

nums[0] < nums[1] > nums[2] < nums[3]...

Example:

nums = [1, 5, 1, 1, 6, 4]

, 一个可能的答案是

[1, 4, 1, 5, 1, 6]

数据保证必定有解。

分析解答

本题有一种简单的做法，先快速排序，然后把最小的一半依次放在奇数位上，最大的一半依次放在偶数位上。算法复杂度是快速排序的复杂度O(NlogN)。仔细思考后发现快速排序不是必要的，只需要找到中位数即可。利用快速排序的思想找中位数的期望时间复杂度是O(N)。为了防止相等的数放在一起，需要注意放置的顺序。笔者采用的方法是依nums长度分两种情况：若长度为奇数，把比中位数小的依次放在0,2,4,...位置，比中位数大的依次放在length-2,length-4,...位置；若长度为偶数，把比中位数小的依次放在length-2,length-4,...位置，比中位数大的依次放在1,3,5,...位置。其余位置填充中位数。这样可以保证中位数一定与较小与较大的数相邻（题目保证一定有解）。

参考程序

更多精彩算法题答案，请登陆jiuzhang.com。





面试官角度分析

因为本题O(N)时间复杂度是额外要求，完成快速排序算法可以达到hire，给出O(N)算法和程序可以达到strong hire。

相关题目

http://www.lintcode.com/en/problem/nuts-bolts-problem/

http://www.lintcode.com/en/problem/partition-array/

点击“阅读原文”，迅速阅读题目，开始刷题。

更多Google 2016 面试题：点击可阅读

Google 2016 面试题2 | 不构造树的情况下验证先序遍历

Google 2016 面试题1 | 数组补丁

关注公众号，回复类别关键字查看相关类别面试题集锦。关键字列表：动态规划，堆，哈希表，数组，二叉树，二分法，智力题，排序，概率，等等；

简介九章算法，团队成员均为硅谷和国内顶尖IT企业工程师。提供算法培训、面试咨询、求职内推。

目前开设课程有九章算法班、系统设计班、Java入门与基础算法班、九章算法强化班。更有android/big data/ios 等即将开课。

目前培训的程序员遍布中国、美国、加拿大、澳大利亚、英国、新加坡等14个国家和地区。

更多详情，登录www.jiuzhang.com，或致信info@jiuzhang.com.

    关注 九章算法