文档章节

若只有4KB内存可用,该如何打印数组中所有重复的元素

一贱书生
 一贱书生
发布于 2016/11/23 09:08
字数 279
阅读 12
收藏 0

/**
 * 功能:给定一个数组,包含1到N的整数,N最大为32000,数组可能含有重复的值,且N的取值不定。
 * 若只有4KB内存可用,该如何打印数组中所有重复的元素。

 */

[java] view plain copy

 

  1. /** 
  2.  * 思路:4KB最多殉职8*4*2^10个比特。比32000大。创建含有32000个比特的位向量,其中每个比特代表一个整数。 
  3.  * 遇到重复元素,打印出来。 
  4.  * @param array 
  5.  */  
  6.   
  7. public static void checkDuplicates(int[] array){  
  8.     BitSet bs=new BitSet(32000);  
  9.     for(int i=0;i<array.length;i++){  
  10.         int num=array[i];  
  11.         int num0=num-1;//Bitser从0开始,数字从1开始  
  12.           
  13.         if(bs.get(num0)){  
  14.             System.out.println(num);//打印原值  
  15.         }else{  
  16.             bs.set(num0);//存入num0  
  17.         }  
  18.     }  
  19. }  

 

 

 

[java] view plain copy

 

  1. class BitSet{  
  2.     int[] bitset;  
  3.     public BitSet(int size){  
  4.         bitset=new int[size>>5];//除以32  
  5.     }  
  6.       
  7.     public boolean get(int pos){  
  8.         int wordNumber=pos>>5;//除以32  
  9.         int bitNumber=pos&(0x1F);//除以32取余数  
  10.         return (bitset[wordNumber]&(1<<bitNumber))!=0;  
  11.     }  
  12.       
  13.     public void set(int pos){  
  14.         int wordNumber=pos>>5;//除以32  
  15.         int bitNumber=pos&(0x1F);//除以32取余数  
  16.         bitset[wordNumber]|=(1<<bitNumber);  
  17.     }  
  18.       
  19. }  


注意:也可参考JAVA内置的BitSet类。

© 著作权归作者所有

共有 人打赏支持
一贱书生
粉丝 19
博文 724
码字总数 600123
作品 0
shell

Shell 脚本 转载自:http://www.imooc.com/article/1131 1) 如何向脚本传递参数 ? ./script argument 例子: 显示文件名称脚本 ./show.sh file1.txtcat show.sh !/bin/bash echo $1 2) 如何在......

eepan
2017/03/13
0
0
海量数据处理的 Top K相关问题

Top-k的最小堆解决方法 问题描述:有N(N>>10000)个整数,求出其中的前K个最大的数。(称作Top k或者Top 10) 问题分析:由于(1)输入的大量数据;(2)只要前K个,对整个输入数据的保存和排序是相...

luanpeng825485697
04/17
0
0
6-Java基础语法-数组之一维数组

数组 为什么要使用数组? 学生成绩排序问题 如果没有数组,我们得定义30个变量。 数组是相同类型的数据按顺序组成的一种引用数据类型 要学习的内容: 一维数组: 声明 创建 初始化 元素的引用 ...

天涯明月笙
08/01
0
0
十道海量数据处理面试题与十个方法大总结

海量数据处理:十道面试题与十个海量数据处理方法总结 本文之总结:教你如何迅速秒杀掉:99%的海量数据处理面试题。 出处:http://blog.csdn.net/vJULYv。 第一部分、十道海量数据处理面试题...

吟啸_徐行
2014/04/02
0
2
99%海量数据处理

http://blog.csdn.net/vjulyv/article/details/7382693 前言 一般而言,标题含有“秒杀”,“99%”,“史上最全/最强”等词汇的往往都脱不了哗众取宠之嫌,但进一步来讲,如果读者读罢此文,...

tantexian
01/15
0
0

没有更多内容

加载失败,请刷新页面

加载更多

20180920 rzsz传输文件、用户和用户组相关配置文件与管理

利用rz、sz实现Linux与Windows互传文件 [root@centos01 ~]# yum install -y lrzsz # 安装工具sz test.txt # 弹出对话框,传递到选择的路径下rz # 回车后,会从对话框中选择对应的文件传递...

野雪球
今天
0
0
OSChina 周四乱弹 —— 毒蛇当辣条

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @ 达尔文:分享花澤香菜/前野智昭/小野大輔/井上喜久子的单曲《ミッション! 健?康?第?イチ》 《ミッション! 健?康?第?イチ》- 花澤香菜/前野智...

小小编辑
今天
6
2
java -jar运行内存设置

java -Xms64m #JVM启动时的初始堆大小 -Xmx128m #最大堆大小 -Xmn64m #年轻代的大小,其余的空间是老年代 -XX:MaxMetaspaceSize=128m # -XX:CompressedClassSpaceSize=6...

李玉长
今天
1
0
Spring | 手把手教你SSM最优雅的整合方式

HEY 本节主要内容为:基于Spring从0到1搭建一个web工程,适合初学者,Java初级开发者。欢迎与我交流。 MODULE 新建一个Maven工程。 不论你是什么工具,选这个就可以了,然后next,直至finis...

冯文议
今天
1
0
RxJS的另外四种实现方式(四)——性能最高的库(续)

接上一篇RxJS的另外四种实现方式(三)——性能最高的库 上一篇文章我展示了这个最高性能库的实现方法。下面我介绍一下这个性能提升的秘密。 首先,为了弄清楚Most库究竟为何如此快,我必须借...

一个灰
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部