leetcode Wiggle Sort II

leetcode Wiggle Sort II

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

Example:
(1) Given nums = [1, 5, 1, 1, 6, 4], one possible answer is [1, 4, 1, 5, 1, 6].
(2) Given nums = [1, 3, 2, 2, 3, 1], one possible answer is [2, 3, 1, 3, 1, 2].

Note:
You may assume all input has valid answer.

Follow Up:
Can you do it in O(n) time and/or in-place with O(1) extra space?

题目地址: leetcode Wiggle Sort II

题意:

给定一个数组,要求进行如下排序: 奇数的位置要大于两边。 如 nums[1] > nums[0]  ,nums[1] > nums[2]

 

思路:

方法一

排序,然后两边分别取,复杂度O(nlogn)

注意排完序之后应该倒着来。比如[4,5,5,6]这个 数据。

Java 7ms

Python 104ms

 

方法二

用快排的思想查找中位数,然后再合并两边。

最坏复杂度O(n^2),平均复杂度O(n)

Java 6ms

 

本文是leetcode 324 Wiggle Sort II  的题解,更多题解可见

https://www.hrwhisper.me/leetcode-algorithm-solution/

本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > leetcode Wiggle Sort II
本文地址:https://www.hrwhisper.me/leetcode-wiggle-sort-ii/

打赏一杯咖啡钱呗

Leetcode , , . permalink.

6 thoughts on “leetcode Wiggle Sort II

  1. 方法1 有问题,感觉

    比如testcase 1,1,2,2,2

    输出为2,2,1,2,1, 但是正确结果应该为2,1,2,1,2

Leave a Reply

Your email address will not be published. Required fields are marked *