Java实现完美洗牌算法

1问题描述有一个长度为2n的数组{a1,a2,a3,…,an,b1,b2,b3,…,bn},希望排序后变成{a1,b1,a2,b2,a3,b3,…,an,bn},请考虑有没有时间复杂度为O(n)而空间复杂度为O(1)的解法。2解决方案2.1位置置换算法下面算法的时间复杂度为O(n),空间复杂度为O(n)。packagecom.liuzhen.practice;publiccl…

大家好,又见面了,我是你们的朋友全栈君。

1 问题描述
有一个长度为2n的数组{a1,a2,a3,…,an,b1,b2,b3,…,bn},希望排序后变成{a1,b1,a2,b2,a3,b3,…,an,bn},请考虑有没有时间复杂度为O(n)而空间复杂度为O(1)的解法。

2 解决方案
2.1位置置换算法

下面算法的时间复杂度为O(n),空间复杂度为O(n)。

package com.liuzhen.practice;

public class Main {
    //对于数组A第i个位置的元素都最终换到了2*i % len的位置
    public void getLocationReplace(String[] A) {
        int len = A.length;
        String[] temp = new String[len];
        for(int i = 1;i < len;i++)
            temp[(2 * i) % len] = A[i];
        for(int i = 1;i < len;i++)
            A[i] = temp[i];
        for(int i = 1;i < len;i = i + 2) {
            String a1 = A[i];
            A[i] = A[i + 1];
            A[i + 1] = a1;
        }
        return;
    }
    
    
    public static void main(String[] args) {
        Main test = new Main();
        String[] A = {"", "a1", "a2", "a3", "a4", "a5", "b1", "b2", "b3", "b4", "b5"};
        test.getLocationReplace(A);
        for(int i = 1;i < A.length;i++)
            System.out.print(A[i]+" ");
    }
}

运行结果:

a1 b1 a2 b2 a3 b3 a4 b4 a5 b5 

2.2 走环算法
下面算法的时间复杂度为O(n),空间复杂度为O(1)。

package com.liuzhen.practice;

public class Main1 {
    
    public void CycleLeader(String[] A, int start, int mod) {
        for(int i = start * 2 % mod;i != start;i = i * 2 % mod) {
            String temp = A[i];
            A[i] = A[start];
            A[start] = temp;
        }
        return;
    }
    
    public void Reverse(String[] A, int start, int end) {
        while(start < end) {
            String temp = A[start];
            A[start++] = A[end];
            A[end--] = temp;
        }
        return;
    }
    
    public void RightRotate(String[] A, int start, int m, int n) {
        Reverse(A, start + m + 1, start + n);
        Reverse(A, start + n + 1, start + n + m);
        Reverse(A, start + m + 1, start + n + m);
        return;
    }
    
    public void PerfectShuffle(String[] A) {
        int len = A.length;
        int n = (len - 1) / 2;
        int start = 0;
        while(n > 1) {
            //第1步:找到2*m = 3^k - 1,使得3^k <= len - 1 < 3^(k + 1)
            int k = 0, m = 1;
            for(;(len - 1) / m >= 3;k++, m = m * 3);
            m = m / 2;
        
            //第2步:把数组中的A[m + 1,...,n + m]那部分循环右移m位
            RightRotate(A, start, m, n);
            
            //第3步:对于长度为2*m的数组,刚好有k个圈,每个圈的头部为3^i
            for(int i = 0, t = 1;i < k;i++, t = t * 3)
                CycleLeader(A, t, m * 2 + 1);
            
            //第4步:对数组后面部分A[2m + 1,...,2n]继续递归上面3步
            start = start + m * 2;
            n = n - m;
            
        }
        //n == 1时
        String temp = A[1 + start];
        A[1 + start] = A[2 + start];
        A[2 + start] = temp;
        for(int i = 1;i < len;i = i + 2) {
            String a1 = A[i];
            A[i] = A[i + 1];
            A[i + 1] = a1;
        }
        return;
    }
    
    public static void main(String[] args) {
        Main1 test = new Main1();
        String[] A = {"", "a1", "a2", "a3", "a4", "a5", "b1", "b2", "b3", "b4", "b5"};
        test.PerfectShuffle(A);
        for(int i = 1;i < A.length;i++)
            System.out.print(A[i]+" ");
    }
}

运行结果:

a1 b1 a2 b2 a3 b3 a4 b4 a5 b5 
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/126209.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • java中类与对象的详解

    java中类与对象的详解

  • GBDT算法详解_gbdt算法

    GBDT算法详解_gbdt算法基本思想GBDT的基本结构是决策树组成的森林,学习方式是梯度提升。具体的讲,GBDT作为集成模型,预测的方式是把所有子树的结果加起来。GBDT通过逐一生成决策子树的方式生成整个森林,生成新子树的过程是利用样本标签值与当前树林预测值之间的残差,构建新的子树。例如,当前已经生成了3课子树了,则当前的预测值为D(x)=d1(x)+d2()x+d3(x),此时我们得到的当前的预测值为D(x)效果并不好,与真正的拟合函数f(x)还有一定的差距。GBDT希望的是构建第四棵子树,使当前树林的预测结果D(x)与第四棵

    2022年10月12日
  • html下拉框内容新增,给html下拉框控件自动添加数据[通俗易懂]

    html下拉框内容新增,给html下拉框控件自动添加数据[通俗易懂]functionAddRow(){varmyTable=tElementById(“ctl00_ContentPlaceHolder1_zjjzzTB”);varnewRowIndex=ws.length;functionAddRow(){varmyTable=tElementById(“ctl00_ContentPlac…

  • 锁文件夹怎么锁_密码锁有没有开锁记录

    锁文件夹怎么锁_密码锁有没有开锁记录1.文件锁可以对将要修改文件的某个部分进行加锁,精确控制到字节通过fcntl()函数来进行设置文件锁fcntl(intfd,intcmd,………);参数:fd:文件描述符cmd

  • for循环中执行顺序_顺序结构选择结构循环结构

    for循环中执行顺序_顺序结构选择结构循环结构今天刷题碰到的一个坑,就是没有注意到for循环的每次判断条件导致的**,也就是for循环的第二句**,每次循环都会执行该判断条件。for循环的表达式一般如下:for(表达式1;表达式2;表达式3){表达式4;}执行的顺序为:第一次循环首先执行表达式1(一般为初始化语句,只执行一次),再执行表达式2(条件判断语句),判断表达式1是否符合表达式2的条件,如果符合,则执行表达式4,……

    2022年10月29日
  • 线程VS进程「建议收藏」

    线程VS进程「建议收藏」什么是线程、什么是进程在Java中要同时执行(如果是单核,准确的说是交替执行)多个任务,使用的是多线程,而要理解线程,我们先要了解什么是进程什么是线程。一般的定义:进程是指在操作系统中正在运行的一个应用程序,线程是指进程内独立执行某个任务的一个单元。怎么理解呢?比如说QQ是是一个进程,如果你在和A朋友语音聊天的同时和B朋友打字聊天,同时还在QQ群下载图片,这三个操作就相当于开启了三个线程,可以说有了线程之后我们设计的程序就可以一边执行A操作,一边执行B操作了。线程和进程有什么区别呢?首先最直观的

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号