🌕🌕🌗 324. 摆动排序 II

难度: 🌕🌕🌗

问题描述

---

解法 1

class Solution {
    public void wiggleSort(int[] nums) {
        // 思路：
        // 数组排序，针对排序后的数组，进行插入
        // 如何插入保证生成摆动序列？
        // 若数组无重复元素，那么 [0, 1, 2, 3, 4] 可以 [mid] 划分为 [left, mid] & [mid + 1, right] 两部分
        // 左半区间长度 >= 右半区间
        // 按照 {left, mid + 1, left + 1, mid + 2, ..., mid, right} 的顺序双指针依次后移交替插入
        // 但是，现在数组中可能存在重复元素，假设为 [0, 1, 1, 1, 4, 5] 此时若还按照传统顺序添加，则生成的序列为
        // {0, 1, 1, 4, 1, 5} 非摆动序列
        // 此时需要转换思路，若为逆序添加，即 {mid, right, mid - 1, right - 1, ..., left, mid + 1}
        // 生成序列为 {1, 5, 1, 4, 0, 1} 满足要求

        int[] clone = nums.clone(); // 浅拷贝
        Arrays.sort(clone); // 无返回数组，说明在 nums 的基础上直接操作，因此为防止生成新数组然后赋值到 nums，直接操作拷贝数组
        int len = nums.length;
        int mid = (len - 1) / 2; // 保证 奇数时 [0, len/2] ；偶数时，[0, len/2 - 1]

        int left = mid;
        int right = len - 1; // 逆序插入
        int index = 0;
        while(index < len) {
            nums[index] = clone[left];
            left --;
            index ++;
            if(right >= mid + 1) { // if 里面也可以用 index < len 代替
                nums[index] = clone[right];
                right --;
                index ++; // 由于 right 区间长度较短，因此左半区间肯定不会超范，右半区间可能超范
            }
        }
    }
}

---

输出 1

---

解法 2 - 变形快排

class Solution {
    public void wiggleSort(int[] nums) {
        // 思路：
        // 我们无需对数组进行完全排序，只需要找到中位数，将其拆分为 [0, mid - 1], [mid, ..., mid], [mid + 1, right] 三部分
        // [mid] 集合中可能存在多个相同的 mid
        // 因此快排后，还需要将 [mid] 尽可能插在 左半区间的右边 & 右半区间的左边
        // 然后双指针逆序插入
        int len = nums.length;
        int mid = (len - 1) / 2; // mid 偏左，但是 mid - left + 1 导致左半区间略大于右半区间
        int[] array = nums.clone();

        // 快排
        mySol(array, 0, len - 1, mid);
        // System.out.println(Arrays.toString(array));
        // 获取中位数的值
        int val = array[mid];
        // 遍历左半区间，将 val 全部放到左半区间的右边
        int i = 0;
        int j = mid - 1;
        while(i < j) {
            if(array[i] == val) {
                // 和最右边元素交换
                swap(array, i, j);
                j --; // 原来的 [j] 已经交换为 val，更新 j
            } else {
                i ++;
            }
        }
        i = mid + 1;
        j = len - 1;
        while(i < j) {
            if(array[j] == val) {
                // 和最左元素交换
                swap(array, i, j);
                i ++;
            } else {
                j --;
            }
        }

        // 双指针逆序拆入，形成 res
        i = mid;
        j = len - 1;
        int index = 0;
        while(index < len) {
            nums[index] = array[i];
            i --;
            index ++;
            if(index < len) {
                nums[index] = array[j];
                j --;
                index ++;
            }
        }
    }

    private void mySol(int[] array, int left, int right, int index) {
        // 递归终止条件
        if(left >= right) {
            return; 
        }
        int monitor = array[left]; // 基准值
        int i = left;
        int j = right;
        while(i < j) {
            while(i < j && array[j] >= monitor) {
                j --; // 需要先进行 j -- 而后 i ++
            }
            while(i < j && array[i] <= monitor) {
                i ++;
            }
            swap(array, i, j);
        }
        // i == j
        swap(array, left, i); // 将基准值交换到中间
        // 与标准快排的区别就在于，每次排序最多只选择排序一边，从而复杂度降低
        if(index == i) {
            return;
        } else if(index > i) {
            mySol(array, i + 1, right, index); // 快排右边
        } else {
            mySol(array, left, i - 1, index);
        }
    }

    private void swap(int[] array, int a, int b) {
        int tmp = array[a];
        array[a] = array[b];
        array[b] = tmp;
    }
}

---

输出 2