如果给定一个int型数组,要求输出其中重复的数字,应该大多数人都能够实现。但是如果数组内数据很多,假设有10亿个,那直接在该数组上进行操作时间复杂度O(n*n)就会变得很大。所以可以通过对byte数组进行操作来降低时间复杂度,步骤分为以下几步:
1、将int型数组内的数据通过恰当的变换赋值给byte数组:int[i]/8为byte数组的下标,int[i]%8的累加赋值给byte【int[i]/8】;
2、对byte数组进行循环判断:如果byte【int[i]/8】为0,说明byte【int[i]/8】中还未赋值,进入赋值步骤,将byte【int[i]/8】转换成8位二进制;否则进入byte【int[i]/8】二进制和int[i]%8二进制的比较,匹配1则输出,否则对其赋值。
/** * 排重的方法 */ public void Repitation_exlusion(int[] in,int n){ int[] a = {1,2,4,8,16,32,64}; char c = '0'; //byte型数组 byte[] bytes = new byte[125]; //byte型数组转换成二进制字符串 String[] s1 = new String[125]; //c1用来存放对应byte数组8位二进制字符串 char[][] c1 = new char[125][8]; //排重 for(int i=0;i<n;i++){ //如果byte数组某一项未出现过则为其赋值 if(c1[in[i]/8]==null){ switch (in[i]%8) { case 0: bytes[in[i]/8]+=(byte)a[0]; break; case 1: bytes[in[i]/8]+=(byte)a[1]; break; case 2: bytes[in[i]/8]+=(byte)a[2]; break; case 3: bytes[in[i]/8]+=(byte)a[3]; break; case 4: bytes[in[i]/8]+=(byte)a[4]; break; case 5: bytes[in[i]/8]+=(byte)a[5]; break; case 6: bytes[in[i]/8]+=(byte)a[6]; break; case 7: c = '1'; break; default: break; } s1[in[i]/8] = ToBinary8(bytes[in[i]/8]); s1[in[i]/8].getChars(1,8,c1[in[i]/8],1); c1[in[i]/8][0] = c; c='0'; } //byte数组中某一项出现了则进行判断 else { if(c1[in[i]/8][7-in[i]%8]=='1') System.out.println(in[i]+"重复出现"); else{ if(in[i]%8!=7){ bytes[in[i]/8]+=(byte)a[in[i]%8]; } else { c1[in[i]/8][0]='1'; } s1[in[i]/8] = ToBinary8(bytes[in[i]/8]); s1[in[i]/8].getChars(1,8,c1[in[i]/8],1); } } } }
/** * 二进制字符串左补0的方法,将字符串转换成8位二进制数 * @param value */ public String ToBinary8(int value){ char[] chars = new char[8]; value = value & 0xFF; for(int i=7;i>=0;i--){ chars[i] = (value%2==1)?'1':'0'; value/=2; } return new String(chars); }
遇到的问题:将128赋给byte数组时,发生了越界的情况,因为byte范围是-128~127,所以另外指定一个字符存储。
改进的代码:
public class RepitationE { /** * @param args */ public static void main(String[] args) { RepitationE re = new RepitationE(); //存放整型数据的int型数组 int[]in={233,56,789,213,6,0,9,871,11,22,56,33,12,11,78,90,999,88,111,345,90,233,122,4,66, 667,33,32,54,47,2}; re.Repitation_exlusion(in,31); } /** * 排重的方法 */ public void Repitation_exlusion(int[] in,int n){ //byte型数组,行数为整除数,列数为余数 byte[][] bytes = new byte[125][8]; //排重 for(int i=0;i<n;i++){ //如果byte数组某一项未出现过则为其赋值 if(bytes[in[i]/8]==null){ bytes[in[i]/8][in[i]%8]=1; } //byte数组中某一项出现了则进行判断 else { if(bytes[in[i]/8][in[i]%8]==1) System.out.println(in[i]+"重复出现"); else{ bytes[in[i]/8][in[i]%8]=1; } } } } }
这样一来不仅免去了创建多个类型数组的麻烦,同时省去了将byte数组内先赋值后转换成二进制的麻烦,代码也简便了很多。
相关推荐
基于hadoop集群系统(也可以在伪分布式系统上运行)系统使用Java编写的倒排索引实现,具有使用停词表功能,使用正则表达式选择规范的单词。代码重构了setup(),map(),combiner(),partitation()和reducer()函数,...
信息检索,倒排记录表的合并算法实现,用户通过提示输入两个倒排记录表,系统自动实现倒排记录表的合并,并将合并结果输出。
根据产线分配的工序得到产线平衡率,根据人员技能效率的不同进行合理的安排,达到产能最大
纹织CAD中图案智能排布算法的实现.pdf
这个是之前学习快排编的,里面包含了生成随机数的代码,仅供参考!
c++倒排索引算法
枚举排序、快速排序、归并排序的串行算法及对应的简单并行算法,java实现,可自由选择线程数。代码仅供参考。
实验四 查找和排序算法实现 1、各种排序算法的实现 2、各种查找算法实现 1、各种排序算法的实现 用随机函数生成16个2位正整数(10~99),实现插入排序、选择排序、冒泡排序、双向冒泡、快速排序、二路归并排序等多种...
基于特征码的网页排重算法的设计与实现,刘新生,厉锟,在大规模新闻抓取中,大量重复或者近似文章也频繁出现,这影响了抓取系统的性能,同时也降低了新闻抓取质量,所以有必要在系统中
C语言实现的倒排索引算法(含全部源码)
快排算法的简单实现。 快速排序是实际运用中用的最多的算法,虽然它在最坏的情况下会达到n^2,但它的平均性能非常好,期望时间复杂度为nlgn,而且隐含的常数因子非常小,并且是原址排序。 快速排序原理:从一组数...
自己写的改进遗传算法的python程序。
spimi算法实现的倒排索引的构建,并且对倒排索引进行了Gamma编码压缩,对词典进行了单一字符串压缩,分别写入了二进制的倒排索引文件和词典文件
快速排序算法C语言实现快速排序算法C语言实现 www.edsionte.com/techblog
这是山东大学大数据实验二,用Hadoop实现文档的倒排索引
根据 求最短路径的遗传算法,改写的排刀算法。
python3.6实现中文语料文本的BSBI算法(倒排索引)索引程序实现。包括中文文本分词,停用词表。
研究生论文 关于APS排程算法,遗传算法
matlab基于遗传算法实现的高效排课系统。有详细的代码
柔性生产线排产算法研究与系统实现_毕业论文.pdf