[Leetcode] Wiggle Sort 摇摆排序

LancerComet 发布于2019-08-14 12:35 / 738人阅读

摘要：就能满足题目要求。代码先将数组排序将数组中一对一对交换交换法复杂度时间空间思路题目对摇摆排序的定义有两部分如果是奇数，如果是偶数，所以我们只要遍历一遍数组，把不符合的情况交换一下就行了。

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

排序法 复杂度

时间 O(NlogN) 空间 O(1)

思路

根据题目的定义，摇摆排序的方法将会很多种。我们可以先将数组排序，这时候从第3个元素开始，将第3个元素和第2个元素交换。然后再从第5个元素开始，将第5个元素和第4个元素交换，以此类推。就能满足题目要求。

代码

public class Solution {
    public void wiggleSort(int[] nums) {
        // 先将数组排序
        Arrays.sort(nums);
        // 将数组中一对一对交换
        for(int i = 2; i < nums.length; i+=2){
            int tmp = nums[i-1];
            nums[i-1] = nums[i];
            nums[i] = tmp;
        }
    }
}

交换法 复杂度

时间 O(N) 空间 O(1)

思路

题目对摇摆排序的定义有两部分：

如果i是奇数，nums[i] >= nums[i - 1]

如果i是偶数，nums[i] <= nums[i - 1]

所以我们只要遍历一遍数组，把不符合的情况交换一下就行了。具体来说，如果nums[i] > nums[i - 1]，则交换以后肯定有nums[i] <= nums[i - 1]。

代码

public class Solution {
    public void wiggleSort(int[] nums) {
        for(int i = 1; i < nums.length; i++){
            // 需要交换的情况：奇数时nums[i] < nums[i - 1]或偶数时nums[i] > nums[i - 1]
            if((i % 2 == 1 && nums[i] < nums[i-1]) || (i % 2 == 0 && nums[i] > nums[i-1])){
                int tmp = nums[i-1];
                nums[i-1] = nums[i];
                nums[i] = tmp;
            }
        }
    }
}

云服务器 GPU云服务器 sort排序算法 Wiggle LeetCode LeetCode_String

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64572.html

[LintCode/LeetCode] Wiggle Sort I & Wiggle Sor

摘要：每隔两位交换一次，如，处理为。难点是会有相等的元素，而要求相邻元素除了外，不能相等。那么就不能取排序后相邻的元素交换，而要和后面的元素交换。例如牺牲空间的做法是，建立一个新数组，按照我们想要的规律放入元素，最后回原数组。 Wiggle Sort Problem Given an unsorted array nums, reorder it in-place such that num...

linkFly 2019-08-14 16:22 评论0 收藏0
[LeetCode] 280. Wiggle Sort

Problem Given an unsorted array nums, reorder it in-place such that nums[0] = nums[2] nums[i-1]) swap(nums, i, i-1); } } } private void swap(int[] nums, int i, int j) { ...

archieyang 2019-08-16 14:00 评论0 收藏0
Wiggle Sort & II

摘要：如果没复杂度的要求，先也可以，再交叉放入数字也可以。交叉的时候注意是按照，降序的。 Wiggle Sort 题目链接：https://leetcode.com/problems... 这道题允许等号，相对简单，有两种方法：1. sort然后交换奇数位和它下一位的元素，2. 不满足条件的时候直接交换可以用递推来说明一下这么做的正确性：假设到第i位之前都满足题目要求的关系现在比较...

Moxmi 2019-08-14 17:18 评论0 收藏0
送给CSS初学者的悬停过渡动画三部曲

摘要：最后，将动画函数选为。的表现状态就是起止过程比较缓慢，中间过渡迅速。褪色效果首先，添加一个褪色的过渡。通过百分比的方式指定动画的进度相对于初始位置右移。同时希望动画持续秒的时长，采用的动画效果。 CSS不一定要写得多么复杂才能实现特殊效果。如下就是三个超级简单的过渡的例子，可能只是几行代码，但是添加到Web应用程序中，却会让它增色不少。showImg(https://segmentfa...

jsliang 2019-08-02 16:14 评论0 收藏0
送给CSS初学者的悬停过渡动画三部曲

摘要：最后，将动画函数选为。的表现状态就是起止过程比较缓慢，中间过渡迅速。褪色效果首先，添加一个褪色的过渡。通过百分比的方式指定动画的进度相对于初始位置右移。同时希望动画持续秒的时长，采用的动画效果。 CSS不一定要写得多么复杂才能实现特殊效果。如下就是三个超级简单的过渡的例子，可能只是几行代码，但是添加到Web应用程序中，却会让它增色不少。showImg(https://segmentfa...

leo108 2019-08-29 18:44 评论0 收藏0