首页
登录 | 注册

[LeetCode] 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].

 

这道题让我们求摆动排序,跟Wiggle Sort II相比起来,这道题的条件宽松很多,只因为多了一个等号。由于等号的存在,当数组中有重复数字存在的情况时,也很容易满足题目的要求。这道题我们先来看一种时间复杂度为O(nlgn)的方法,思路是先给数组排个序,然后我们只要每次把第三个数和第二个数调换个位置,第五个数和第四个数调换个位置,以此类推直至数组末尾,这样我们就能完成摆动排序了,参见代码如下:

 

解法一:

// Time Complexity O(nlgn)
class Solution {
public:
    void wiggleSort(vector<int> &nums) {
        sort(nums.begin(), nums.end());
        if (nums.size() <= 2) return;
        for (int i = 2; i < nums.size(); i += 2) {
            swap(nums[i], nums[i - 1]);
        }
    }
};

 

这道题还有一种O(n)的解法,根据题目要求的nums[0] <= nums[1] >= nums[2] <= nums[3]....,我们可以总结出如下规律:

当i为奇数时,nums[i] >= nums[i - 1]

当i为偶数时,nums[i] <= nums[i - 1]

那么我们只要对每个数字,根据其奇偶性,跟其对应的条件比较,如果不符合就和前面的数交换位置即可,参见代码如下:

 

解法二:

// Time Complexity O(n)
class Solution {
public:
    void wiggleSort(vector<int> &nums) {
        if (nums.size() <= 1) return;
        for (int i = 1; i < nums.size(); ++i) {
            if ((i % 2 == 1 && nums[i] < nums[i - 1]) || (i % 2 == 0 && nums[i] > nums[i - 1])) {
                swap(nums[i], nums[i - 1]);
            }
        }
    }
};

 

类似题目:

Wiggle Sort II

 

参考资料:

https://segmentfault.com/a/1190000003783283

http://www.cnblogs.com/jcliBlogger/p/4797531.html

 

LeetCode All in One 题目讲解汇总(持续更新中...)

 


相关文章

  • 一.前言 在日常开发中,我们经常会碰到需要在运行时才知道对象个数的情况,这种情况不能使用数组,因为数组是固定数量的,这个时候我们就会使用集合,因为集合可以存储数量不确定的对象. 集合类是特别有用的工具类,不仅可以存储数量不等的对象,还可以实 ...
  • MongoDB【快速入门】
    1.MongDB 简介 MongoDB(来自于英文单词"Humongous",中文含义为"庞大")是可以应用于各种规模的企业.各个行业以及各类应用程序的开源数据库.作为一个适用于敏捷开发的数据库,Mo ...
  • 实验四实验报告
    实验结论 Part 1 数组将类型相同的一组数据在内存中连续存放,由实验可看出数组中元素的内存地址是连续的,不同类型数据计算机为其分配的内存空间是不同的. Part 2 定义一维数组a,须指明它包含的元素个数和元素类型,通过数组名和下标的形 ...
  • 实验4(2019.4.23)
    [实验结论] 一.对Part1-Part4的总结. 1.数组名作为函数参数时,形参.实参的语法形式书写注意事项. 这一点在书本上P154—P158有详细说明,但是叙述过于冗杂,所以借用“实验4.pdf”中的内容总结: (1)函数声明和函数定 ...
  • 基于mapreduce实现图的三角形计数
    源代码放在我的github上,想细致了解的可以访问:TriangleCount on github 一.实验要求 1.1 实验背景         图的三角形计数问题是一个基本的图计算问题,是很多复杂网络分析(比如社交网络分析)的基础.目前 ...
  • jenkins定位GitLab推送的最新Webhook中push event来自哪一个分支
    转载请标明出处:http://www.cnblogs.com/zblade/ 一.调研目的 jenkins可以和GitLab搭档,每当GitLab上有commit的时候,都可以触发jenkins执行相关的操作,具体的实现,可以参看我前面的博 ...

2020 cecdns.com webmaster#cecdns.com
12 q. 0.063 s.
京ICP备10005923号