[Leetcode] Wiggle Sort 搖擺排序

LancerComet 發(fā)布于2019-08-14 12:35 / 876人閱讀

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

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

排序法 復(fù)雜度

時(shí)間 O(NlogN) 空間 O(1)

思路

根據(jù)題目的定義，搖擺排序的方法將會(huì)很多種。我們可以先將數(shù)組排序，這時(shí)候從第3個(gè)元素開始，將第3個(gè)元素和第2個(gè)元素交換。然后再從第5個(gè)元素開始，將第5個(gè)元素和第4個(gè)元素交換，以此類推。就能滿足題目要求。

代碼

public class Solution {
    public void wiggleSort(int[] nums) {
        // 先將數(shù)組排序
        Arrays.sort(nums);
        // 將數(shù)組中一對(duì)一對(duì)交換
        for(int i = 2; i < nums.length; i+=2){
            int tmp = nums[i-1];
            nums[i-1] = nums[i];
            nums[i] = tmp;
        }
    }
}

交換法 復(fù)雜度

時(shí)間 O(N) 空間 O(1)

思路

題目對(duì)搖擺排序的定義有兩部分：

如果i是奇數(shù)，nums[i] >= nums[i - 1]

如果i是偶數(shù)，nums[i] <= nums[i - 1]

所以我們只要遍歷一遍數(shù)組，把不符合的情況交換一下就行了。具體來說，如果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++){
            // 需要交換的情況：奇數(shù)時(shí)nums[i] < nums[i - 1]或偶數(shù)時(shí)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;
            }
        }
    }
}