[Leetcode] Wiggle Sort 搖擺排序

LancerComet 發布于2019-08-14 12:35 / 877人閱讀

摘要：就能滿足題目要求。代碼先將數組排序將數組中一對一對交換交換法復雜度時間空間思路題目對搖擺排序的定義有兩部分如果是奇數，如果是偶數，所以我們只要遍歷一遍數組，把不符合的情況交換一下就行了。

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/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