擺動排序 I

給你一個沒有排序的數(shù)組，請將原數(shù)組就地重新排列滿足如下性質(zhì)

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

允許相鄰元素相等

思路

先對數(shù)組進(jìn)行排序，然后依次把兩兩相鄰的元素進(jìn)行交換，最終成為一個波動遞增的數(shù)列，滿足題目要求

實(shí)現(xiàn)

public void wiggleSort(int[] nums) {
        // write your code here
        //先對數(shù)組進(jìn)行排序
        Arrays.sort(nums);

        //然后依次把i和i+1的元素進(jìn)行交換，就可以得到一個擺動排序
        for (int i=1;i<nums.length-1;i=i+2) {
            int temp = nums[i];
            nums[i] = nums[i + 1];
            nums[i + 1] = temp;
        }
    }

擺動排序 II

給你一個數(shù)組nums，將它重排列如下形式

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

樣例

給出 nums = [1, 5, 1, 1, 6, 4],一種方案為 [1, 4, 1, 5, 1, 6].

給出 nums = [1, 3, 2, 2, 3, 1],一種方案為 [2, 3, 1, 3, 1, 2].

思路

先元素排序，然后把元素按照中心軸切分開，把前半部分元素正向插入1,3,5...，把后半部分元素正向插入2,4,6...

你可以想象一個直角三角形，從中間切開之后，把較小的部分穿插進(jìn)較大的部分，形成一個波動的圖像。

實(shí)現(xiàn)

public void wiggleSort(int[] nums) {
        // write your code here
        //邊界
        if (nums.length <= 1) {
            return;
        }
        //先對數(shù)組進(jìn)行排序
        Arrays.sort(nums);

        //取中心軸
        int axis = nums.length / 2;

        //創(chuàng)建結(jié)果數(shù)組
        int[] result = new int[nums.length];

        if (nums.length % 2 == 0) {
            //如果數(shù)組長度為偶數(shù)
            //把前半部分元素正向插入1,3,5...
            int j = 0;
            for (int i = 0; i < axis; i++) {
                result[j] = nums[i];
                j = j + 2;
            }
            //把后半部分元素正向插入2,4,6...
            int k = 1;
            for (int i = axis; i < nums.length; i++) {
                result[k] = nums[i];
                k = k + 2;
            }
        } else {
            //如果數(shù)組長度為奇數(shù)
            //把前半部分元素正向插入1,3,5...
            int j = 0;
            for (int i = 0; i <= axis; i++) {
                result[j] = nums[i];
                j = j + 2;
            }
            //把后半部分元素正向插入2,4,6...
            int k = 1;
            for (int i = axis + 1; i < nums.length; i++) {
                result[k] = nums[i];
                k = k + 2;
            }
        }


        for (int i=1;i<nums.length;i++) {

            if (result[i] == result[i - 1]) {
                //假如出現(xiàn)了這種邊界情況 4 5 5 6 要想辦法轉(zhuǎn)化成 5 6 4 5
                //把6移到第一個5的位置
                int temp = result[i + 1];
                result[i + 1] = result[i - 1];
                result[i - 1] = temp;
                //把4移到第二個5的位置
                int tepo = result[i];
                result[i] = result[i - 2];
                result[i - 2] = tepo;
            }
        }

        System.arraycopy(result,0,nums,0,nums.length);
    }

基于上一個思路的代碼改進(jìn)

較上一思路，這次采用了從大端到小端的逆向插入
相當(dāng)于把上一個思路中的遞增三角形進(jìn)行了水平翻轉(zhuǎn)，變成一個遞減三角形，分成兩半，穿插成一個波動圖像
同時也巧妙避開了 4 5 5 6 的問題

public static void wiggleSort(int[] nums) {
        int n = nums.length;
        if(n == 0) return ;
        int[] a = Arrays.copyOfRange(nums,0,n);
        Arrays.sort(a);
        int k = 0 , p = (n-1)/2, q = n-1;
        boolean sign = true;
        //sign控制交替賦值
        while(k < n){
            if(sign) nums[k++]=a[p--];
            else nums[k++]=a[q--];
            sign = !sign;
        }
        printArray(nums);
    }

如果覺得文章對你有幫助的話，不要忘了打賞小編喲