1.完美洗牌问题

题目描述：
给定一个长度为偶数的数组arr，假设长度为: N*2
左部分：arr[L1...Ln]
右部分：arr[R1...Rn]
请把arr调整成arr[L1,R1,L2,R2,L3,R3,...,Ln,Rn]

要求时间复杂度O(N)，额外空间复杂度O(1)

2.思路

题目要求额外空间复杂度为1，那么就要求必须我们使用公式计算出来任意一个下标的元素应该要去的位置，我们可以使用下标循环推，就是一开始元素获取到正确位置怼过去，原本在那个位置的存住，然后继续哪个位置的算推到他对应的位置，… 直到推完

//1.计算出要去的位置
int goIndex = getGoIndex(arr[i]);
//2.占据goIndex的位置
arr[goIndex] = arr[i]
//3.获取goIndex要去的位置
int nextGoIndex = getGoIndex(arr[goIndex])
//4.以此循环下去
..

存在的问题：

一直替换的过程，可能形成环，导致中间有些元素没有去处理
不一定是一个大环，而是有可能是多个小环，而且每个小环一定不相交

3.结论

针对这样有环的情况，我们需要找到所有的入环点，然后依次调用公式，把元素放到正确的位置，在这里，需要引入一个结论：

结论1: 当数组长度满足N = 3^(k) - 1 的时候，环的出发点1,3,9...3^(k-1)

例如：
1.当数组长度为8的时候，环的出发点分别是：1，3
2.当数组长度为13的时候，环的出发点分别是：1，3，9

但是：如果元素的长度不满足公式的长度怎么办？例如数组的长度为12，不满足3^(k) - 1

结论2: 如果数组长度不满足这个公式，则需要获取整个数组离满足这个公式最近的长度来进行操作

例如：长度为12的数组距离最近的一个满足公式的位置是8（即：3^2 - 1)，那么可以将这个长度为12的数组分成两部分，一部分长度是8，另外一部分长度是4。

1.长度为12的数组
[L1，L2，L3，L4，L5, L6, R1, R2, R3, R4, R5, R6]

2.应该是左边四个（L1，L2，L3，L4），右边四个（R1，R2，R3，R4）

3.把区间[L5,L6]和区间[R1,R2,R3,R4]做一次反转得到：
[L1，L2，L3，L4，R1, R2, R3, R4][L5, L6, R5, R6]

4.可以通过公式得到入环点是L1和L3，然后利用入环点调用公式得到每个位置调整后的位置
[R1, L1，R2, L2，R3, L3，R4, L4][L5, L6, R5, R6]

5. 剩余长度为4的数组，同样找到离4最近的，满足条件的长度是2（即：3^1 - 1), 然后将长度为4的数组同样做上述处理，得到
[L5, R5, L6, R6]

6. 入环点为L5, 调换位置后为：
[R1, L1，R2, L2，R3, L3，R4, L4][R5, L5][L6, R6]

7. 剩余长度为2，入环点为L6,调换位置后为：
[R1, L1，R2, L2，R3, L3，R4, L4][R5, L5][R6, L6]

4.应用

4.1 左旋转字符串

题目：将一个字符串password的前 target 个字符按原顺序移动至字符串末尾并返回旋转后的字符串

思路：

根据target 分为2个区域
每个区域各自逆序
最后整体再逆序

    public String dynamicPassword(String password, int target) {
        if(password == null || password.equals("")){
            return null;
        }
        if(password.length() < target){
            return null;
        }
        char[] arr = password.toCharArray();
        //各自区域逆序
        reserve(arr, 0, target-1);
        reserve(arr, target, arr.length-1);
        //整体逆序
        reserve(arr,0, arr.length-1);
        return new String(arr);
    }

    private void reserve(char[] arr, int l, int r){
        while (l<r){
            swap(arr,l,r);
            l++;
            r--;
        }
    }

    private void swap(char[] arr, int l, int r){
        char tmp = arr[l];
        arr[l] = arr[r];
        arr[r] = tmp;
    }

4.2 重新排列数组

题目：
给你一个数组 nums ，数组中有 2n 个元素，按 [x1,x2,...,xn,y1,y2,...,yn] 的格式排列。
请你将数组按 [x1,y1,x2,y2,...,xn,yn] 格式重新排列，返回重排后的数组。

思路：

先按照完美洗牌，调整为[y1,x1,y2,x2,...,yn,xn]
再两两逆序

    public int[] shuffle(int[] nums, int n) {
        //1.先调整为[y1,x1,y2,x2,...,yn,xn]
        shuffle(nums);
        //2.再两两逆序
        for (int i = 0; i < nums.length; i+=2) {
            reserve(nums, i ,i+1);
        }
        return nums;
    }

    public void shuffle(int[] arr) {
        //必须为偶数
        if (arr == null || arr.length == 0 || (arr.length & 1) != 0) {
            return;
        }
        shuffle(arr, 0, arr.length - 1);
    }

    /**
     * 在nums[l,r]上做完美洗牌
     * @param nums
     * @param l
     * @param r
     */
    public void shuffle(int[] nums, int l,int r){
        while (r - l + 1 >0){
            //切成一块一块的解决，每块满足（3^k）- 1的长度
            int len = r - l + 1;
            //从3的0次方开始
            int base = 3;
            int k = 1;
            //找到离（3^k）- 1最近的数
            while (base <= (len + 1)/3){
                base *= 3;
                k++;
            }
            //当前要解决的长度的一半
            int half = (base-1)/2;
            //中点位置就是旋转点的位置
            int mid = (l + r)/2;
            //左旋转
            rotate(nums, l+half, mid + half, mid);
            //循环下标替换
            cycleSwap(nums, l, base - 1, k);
            //继续解决，剩余的部分
            l = l + base -1;
        }
    }


    public void rotate(int[] arr, int l, int r, int mid){
        reserve(arr,l, mid);
        reserve(arr, mid+1, r);
        reserve(arr,l,r);
    }

    private void reserve(int[] arr, int l, int r){
        while (l<r){
            swap(arr,l,r);
            l++;
            r--;
        }
    }

    private void swap(int[] arr, int l, int r){
        if (arr == null || arr.length <= 1 || l == r) {
            return;
        }
        arr[l] = arr[l] ^ arr[r];
        arr[r] = arr[l] ^ arr[r];
        arr[l] = arr[l] ^ arr[r];
    }

    private void cycleSwap(int[] arr, int start, int len, int k){
        /**
         * 入环点为trigger-1
         */
        for (int i = 0, trigger = 1; i < k; i++, trigger *= 3) {
            int pre = arr[start + trigger - 1];
            int next = findNextIndex(trigger, len);
            while (next != trigger) {
                int t = arr[next + start - 1];
                arr[next + start - 1] = pre;
                pre = t;
                next = findNextIndex(next, len);
            }
            arr[next + start - 1] = pre;
        }
    }

    //i位置下一个位置应该去哪里，i就是trigger，i从1开始，而不是从0开始!!!
    private static int findNextIndex(int i, int N) {
        // return (2 * i) % (N + 1);
        if (i <= N / 2) {
            return 2 * i;
        }
        return (i - N / 2) * 2 - 1;
    }

4.3 摆动排序

题目：
给你一个整数数组 nums，将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]... 的顺序

思路：

对数组进行排序
如果是奇数，那么从1～nums.length-1 进行完美洗牌
如果是偶数，那么从0～nums.length-1 进行完美洗牌
最后在两两进行逆序

    public void wiggleSort(int[] nums) {
        if(nums == null || nums.length == 1){
            return;
        }
        Arrays.sort(nums);
        if((nums.length & 1) == 1){
            //奇数
            shuffle(nums, 1, nums.length-1);
        }else{
            //偶数
            shuffle(nums, 0, nums.length-1);
        }
        reserve(nums, 0, nums.length-1);
    }

完美洗牌