[LintCode/LeetCode] Wiggle Sort I & Wiggle Sor

linkFly 发布于2019-08-14 16:22 / 2261人阅读

摘要：每隔两位交换一次，如，处理为。难点是会有相等的元素，而要求相邻元素除了外，不能相等。那么就不能取排序后相邻的元素交换，而要和后面的元素交换。例如牺牲空间的做法是，建立一个新数组，按照我们想要的规律放入元素，最后回原数组。

Wiggle Sort Problem

Given an unsorted array nums, reorder it in-place such that

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

Example

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

Note

每隔两位交换一次，如【1 2 3 4 5 6】，处理为【1 3 2 5 4 6】。

Solution

public class Solution {
    public void wiggleSort(int[] nums) {
        Arrays.sort(nums);
        for (int i = 2; i < nums.length; i+=2) {
            int temp = nums[i];
            nums[i] = nums[i-1];
            nums[i-1] = temp;
        }
        return;
    }
}

Wiggle Sort II Problem

Given an unsorted array nums, reorder it such that

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

Example

Given nums = [1, 5, 1, 1, 6, 4], one possible answer is [1, 4, 1, 5, 1, 6].

Given nums = [1, 3, 2, 2, 3, 1], one possible answer is [2, 3, 1, 3, 1, 2].

Note

难点是会有相等的元素，而要求相邻元素除了wiggle外，不能相等。
那么就不能取排序后相邻的元素交换，而要和后面的元素交换。例如：

//1 2 3 4 5 6
//3 6 2 5 1 4

牺牲空间的做法是，建立一个新数组temp，按照我们想要的规律放入元素，最后copy回原数组nums。
简单的思路就是，假设nums里有n个数，我们循环n/2次或者n/2+1次，每次循环里为temp添加两个数（n为奇数时，最后一次循环只添加一个数）。最后用System.arraycopy(sourceArray, 0, targetArray, 0, targetArray.length).

Solution

耗时浪费空间法

public class Solution {
    public void wiggleSort(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length, mid = (n-1)/2, index = 0;
        int[] temp = new int[n];
        for (int i = 0; i <= mid; i++) {
            temp[index] = nums[mid-i];
            if (index+1 < n) {
                temp[index+1] = nums[n-1-i];
            }
            index += 2;
        }
        System.arraycopy(temp, 0, nums, 0, n);
    }
}

私有云 GPU服务器 Wiggle insertion-sort i+1&lti java sort()

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

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

Wiggle Sort &amp; II

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

Moxmi 2019-08-14 17:18 评论0 收藏0
[Leetcode] Wiggle Sort 摇摆排序

摘要：就能满足题目要求。代码先将数组排序将数组中一对一对交换交换法复杂度时间空间思路题目对摇摆排序的定义有两部分如果是奇数，如果是偶数，所以我们只要遍历一遍数组，把不符合的情况交换一下就行了。 Wiggle Sort Given an unsorted array nums, reorder it in-place such that nums[0] = nums[2] = nums[i ...

LancerComet 2019-08-14 12:35 评论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
leetcode376. Wiggle Subsequence

摘要：题目要求扭动序列是指数组中的相邻两个元素的差保证严格的正负交替，如数组中相邻两个元素的差为，满足扭动序列的要求。现在要求从一个数组中，找到长度最长的扭动子序列，并返回其长度。即前一个元素和当前元素构成下降序列，因此代码如下题目要求 A sequence of numbers is called a wiggle sequence if the differences between ...

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

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

jsliang 2019-08-02 16:14 评论0 收藏0