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)


相关推荐

  • 单例模式(Singleton)应用场景和优缺点

    单例模式(Singleton)应用场景和优缺点单例(Singleton)模式 也叫单态模式概述:单例(Singleton)模式要求一个类有且仅有一个实例,并且提供了一个全局的访问点。这就提出了一个问题:如何绕过常规的构造器,提供一种机制来保证一个类只有一个实例?客户程序在调用某一个类时,它是不会考虑这个类是否只能有一个实例等问题的,所以,这应该是类设计者的责任,而不是类使用者的责任。 从另一个角度来说,Singleton模式其实也是一…

  • jenkins自定义构建参数_git创建远程仓库分支

    jenkins自定义构建参数_git创建远程仓库分支前言当我们的自动化项目越来越多的时候,在代码仓库会提交不同的分支来管理,在用jenkins来构建的时候,我们希望能通过参数化构建git仓库的分支。下载安装GitParameter插件系统管理-

  • f stream_Streaming

    f stream_Streamingc++文件流基本用法
    C++学习笔记2010-05-2015:07:46阅读57评论0  字号:大中小 订阅
    c++的文件流处理其实很简单,前提是你能够理解它。文件流本质是利用了一个buffer中间层。有点类似标准输出和标准输入一样。
      c++IO的设计保证IO效率,同时又兼顾封装性和易用性。本文将会讲述c++文件流的用法。
      有错误和疏漏的地方,欢迎批评指证。
      需要包含的头文件:
      名字空间:std

  • sql server 2005卸载教程_sql卸载工具

    sql server 2005卸载教程_sql卸载工具如果您要安装新版的sql就必须先完整的卸载sql2005,如果你按照常规的方法是不能完整的卸载sql2005,从而会引起安装的时候说sql已经挂起的错误,sql2005卸载工具(sqlserver2005卸载工具),是一个帮你完整的清理已经安装的sql的工具。MicrosoftSQLServer2005是一个全面的数据库平台,使用集成的商业智能(BI)工具提供了企业级的数据管理。Mi…

  • linux修改smb端口_sftp默认端口号是多少

    linux修改smb端口_sftp默认端口号是多少本文介绍如何在Linux操作系统中更改默认的SFTP端口,支持Ubuntu、CentOS等发行版,同时还将向您展示如何配置防火墙以允许在新端口上使用。先声明的一点是不要将SFTP与FTPS混淆,因为两种协议具有相同的目的,FTPS代表FTPSecure,它是对标准FTP协议的扩展,支持TLS。简介SFTP(SSH文件传输协议)是一种安全文件协议,用于通过加密连接在两个主机之间传输文件,它还允许您…

  • windows cmd进入mysql[通俗易懂]

    windows cmd进入mysql[通俗易懂]在DOS命令窗口输入 mysql-hlocalhost-uroot-p回车 进入mysql数据库,其中-h表示服务器名,localhost表示本地;-u为数据库用户名,root是mysql默认用户名;-p为密码,如果设置了密码,可直接在-p后链接输入,如:-p123456,用户没有设置密码,显示Enterpassword时,直接回车即可。注意,如果你的mysql没有安装在C盘下

发表回复

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

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