【LeetCode】摆动排序 [M]（数组）

280. 摆动排序 - 力扣（LeetCode）

一、题目

给你一个的整数数组 nums, 将该数组重新排序后使 nums[0] <= nums[1] >= nums[2] <= nums[3]... 
输入数组总是有一个有效的答案。

示例 1：

输入：nums = [3,5,2,1,6,4]
输出：[3,5,1,6,2,4]
解释：[1,6,2,5,3,4]也是有效的答案

示例 2：​​​​​​​

输入：nums = [6,6,5,6,3,8]
输出：[6,6,5,6,3,8]

提示：​​​​​​​

• 1 <= nums.length <= 5 * 104
• 0 <= nums[i] <= 104

• 输入的 nums 保证至少有一个答案。

二、代码

class Solution {
    public void wiggleSort(int[] nums) {
        // 过滤无效参数
        if (nums == null || nums.length == 0) {
            return;
        }
        // 这道题需要先排序，因为这道题本意并不是说要将数组中的数据按照完美洗牌两两交错着重排一遍，而是说按照小大小大小大这样的间隔顺序排列，而我们的完美洗牌代码只是按照位置来两两交错，
        // 如果想要左到题目要求的小大小大小大这种按照大小交错，就需要先把数组搞成有序的，然后再调用我们的完美洗牌代码就可以了。
        // 还要注意的是这个是280. 摆动排序，这个题要求是nums[0] <= nums[1] >= nums[2] <= nums[3]... 是带等号的，所以用完美洗牌的代码可以求解，
        // 但是324. 摆动排序 II这道题是不带等号的，所以就还需要考虑将相等的数不能挨着，完美洗牌问题做不到这个，完美洗牌只是单纯的将位置来进行交错排列，但是无法根据它们的大小来调整顺序，所以完美洗牌代码是有可能将两个相等的数挨着的
        // 假设这个排序是额外空间复杂度O(1)的，当然系统提供的排序并不是，你可以自己实现一个堆排序
        Arrays.sort(nums);
        int n = nums.length;
        // 这道题本身并没有限制数组长度是否是偶数，而我们完美洗牌代码必须保证传入的数组长度是偶数才可以，所以下面还需要做数组长度的奇偶判断，做相应的处理
        // 偶数情况，因为力扣题目要求的完美问题是小大小大小大这样间隔的，但是如果我们的数组是递增的，用我们这个完美洗盘的代码搞出来的4 1 5 2 6 3，但是我们最后想要的其实是1 4 2 5 3 6
        // 所以偶数情况在用我们的代码完成完美洗牌后，还需要两两为一组，在组内交换两个数的位置，才是力扣这道题最后的答案。
        if ((n & 1) == 0) {
            // 先进行完美洗牌的前半部分和后半部分的交叉排序
            shuffle(nums, 0, n - 1);
            // 在按照两个为一组，在内部交换两数位置，这样得到的结果就符合本题要求了
            int temp;
            for (int i = 0; i < n; i+= 2) {
                temp = nums[i];
                nums[i] = nums[i + 1];
                nums[i + 1] = temp;
            }
        // 奇数情况   例如1 2 3 4 5，第一个位置的1保持不动，然后去对后面四个数做下标循环怼，因为后面四个是偶数，符合下标循环怼的要求，最后结果正好是 1 4 2 5 3，是我们要的答案
        } else {
            // 将1~n-1范围上做完美洗牌，下标0位置不动，最后的结果就是本题要的结果。
            shuffle(nums, 1, n - 1);
        }
    }
    /**
     * 完美洗牌问题的算法模板，这是整个代码的核心
     * nums：数组长度必须为偶数
     * 在nums[l...r]上做完美洗牌的调整（nums[l...r]范围上一定要是偶数个数字）
     */
    public void shuffle(int[] nums, int l, int r) {
        // 切成一块一块的解决，每一块的长度满足(3^k)-1
        // 如果此时r > l，就说明此时还有范围要搞（l==r有1个数，也就不需要再变动了，符合公式要求的最低长度也是2），当r和l错过去了，就说明已经完成全部位置的操作了
        while (r > l)  {
            // 当前要处理的r - l范围上的数据
            // 长度为n
            int n = r - l + 1;
            
            // 计算小于等于len并且是离n最近的，满足(3^k)-1的数
			// 也就是找到最大的k，满足3^k <= n+1
            int k = 1; // 初始k为1
            int base = 3; // 初始值
            // 保证3^k <= n+1
            // 要记住这个方法，就是求3次幂的时候直接用循环滚下去，利用之前求出来的结果，只需要再乘一个3就行了，这样效率可以更高一些，比每一轮都重新用Math.pow求快很多
            while (base * 3 - 1 <= n) {
                base *= 3;
                k++;
            }
            // 此时我们就先处理长度为base - 1长度的范围，至于剩下的长度留到后面的循环去弄。base - 1满足3^k -1
            // 下面这个流程就是将符合要求的前k个数移动到数组的最前面，下面的流程其实举个具体的例子或者直接看笔记就能明白了
			// 当前要解决长度为base-1的块，一半就是再除2
            int half = (base - 1) >> 1;
            // [L..R]的中点位置
            int mid = (l + r) >> 1;
            // 要旋转的左部分为[L+half...mid], 右部分为arr[mid+1..mid+half]
			// 注意在这里，arr下标是从0开始的
            rotate(nums, l + half, mid, mid + 1, mid + 1 + half - 1);
 
            // 旋转完成后，从l开始算起，长度为base-1的部分进行下标连续推
            // 从l位置开始，往右n的长度这一段，做下标循环怼
	        // 每一个环的起始位置依次为1,3,9...
            // 当前要处理数组的起始位置就是l，在后面算数组中真实下标时，都要加上l
 
            // 当前要处理数组的长度
            int len = base - 1;
            // trigger就是在我们结论中起始位置的下标，注意是从1开始的，如果想要求出来在数组中真实对应的下标，应该用start + trigger - 1(也就是用此时数组的左边界l加上trigger再减1，因为trigger是从1开始的，多算了一个)
            // 找到每一个出发位置trigger，一共k个（1、3、9...3^(k - 1)）
            // 每一个trigger都进行下标连续推
            // 出发位置是从1开始算的，而数组下标是从0开始算的。
            // i是为了来控制求3^(k - 1)，i会控制循环一共只会执行k次，但是因为trigger是从1开始的，所以最终其实只会有k-1个3相乘，也就得到了3 ^ (k - 1)
            for (int i = 0, trigger = 1; i < k; i++, trigger *= 3) {
                // 当前遍历到的在数组中真实的下标位置是l + trigger - 1
                // 我们要将nums[l + trigger - 1]放到下一个要去的位置，所以这里要将该位置的值记录一下
                int preValue = nums[l + trigger - 1];
                // 根据我们的结论公式，算出来下一个要在什么位置，注意这个位置并不是真实的数组下标位置
                int cur = modifyIndex(trigger, len);
                // 每一轮循环时trigger就相当于这一次下标循环怼的起始位置，只要是循环过程中下标再次回到trigger，就说明这个环已经遍历完一遍了
                while (cur != trigger) {
                    // 当前来到的位置在数组的真实下标l + cur - 1，（l就是当前处理范围的最左边界下标）
                    int tmp = nums[l + cur - 1];
                    // 将上一个位置的值放到当前位置上
                    nums[l + cur - 1] = preValue;
                    // 将当前位置的值作为下一轮的上一个位置的值，我们要将nums[cur + l - 1]放到下一个位置上去
                    preValue = tmp;
                    // 根据公式计算下一个位置
                    cur = modifyIndex(cur, len);
                }
                // 当cur == trigger时会跳出循环，但此时trigger位置的值还没有放，所以要将preValue赋值给当前环的起始位置l + cur  - 1
                nums[l + cur - 1] = preValue;
            }
 
            // 解决了前base-1的部分，剩下的部分继续处理，将要处理范围的左边界设置为l + base - 1，继续循环
            l = l + base - 1;
        }
    }
 
    // 完美洗牌问题的公式结论，这个记住即可，不用管他的证明
    // 当前来到index位置，当前进行下标循环堆的数组长度是n，返回要将index位置的数据移动到哪个下标上
    public int modifyIndex(int index, int n) {
        // 分段函数，根据index不同来返回不同的下一个位置的下标
        if (index <= n / 2) {
            return index * 2;
        } else {
            return (index - n / 2) * 2 - 1;
        }
    }
 
    // 将l1~r1和l2~r2两个部分做整体交换
    // 这两个部分是连续的，即r1 + 1 = l2
    public void rotate(int[] nums, int l1, int r1, int l2, int r2){
        // 先对这两个部分自己内部做逆序
        reverse(nums, l1, r1);
        reverse(nums, l2, r2);
        // 然后再把这两个部分的整体进行逆序
        reverse(nums, l1, r2);
    }
    // 对数组nums内的l~r范围进行逆序
    public void reverse(int[] nums, int l, int r) {
        int temp;
        while (l < r) {
            temp = nums[l];
            nums[l++] = nums[r];
            nums[r--] = temp; 
        }
    }
}

三、解题思路 

一个位置要去哪儿是一个简单公式可以确定的。

这里我们就用R1L1R2L2这种形式为基础，来给一个公式。

左半部分的数要去2*i位置；右半部分的数要去（i - N / 2）* 2 - 1。规定下标从1开始。