文档章节

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

一贱书生
 一贱书生
发布于 2016/11/23 09:08
字数 279
阅读 15
收藏 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
私信 提问
海量数据处理的 Top K相关问题

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

luanpeng825485697
04/17
0
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
【程序猿必备】数据结构与算法精选面试题

有很多计算机科学技术专业的毕业生和程序员申请在Uber和Netflix这样的初创公司、谷歌和阿里巴巴这样的大公司以及Infosys或Luxsoft等以服务为基础的公司从事编程、编码和软件开发工作,但他们...

【方向】
10/07
0
0
6-Java基础语法-数组之一维数组

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

天涯明月笙
08/01
0
0
映射队列(上)

这篇文章主要介绍Mushroom(这是我项目的名称,一个多线程索引,即将成为分布式索引?)里面一个非常关键的数据结构——映射队列。 我没有在开源代码中见到过类似的队列,所以也许这可以算是...

UncP
2017/05/12
0
0

没有更多内容

加载失败,请刷新页面

加载更多

使用 React 和 Vue 创建相同的应用,他们有什么差异?

在工作中应用 Vue 之后,我对它有了相当深刻的理解。 不过,俗话说「外国的月亮比较圆」,我好奇「外国的」 React 是怎么样的。 我阅读了 React 文档并观看了一些教程视频,虽然它们很棒,但...

阿K1225
9分钟前
0
0
如何使用Kubernetes的configmap通过环境变量注入到pod里

在Kubernetes官网里,有这样一篇文章,提到了Kubernetes里的一个最佳实践就是把应用代码同配置信息分开,一种方式就是使用Kubernetes 1.2里引入的configmap概念。 https://kubernetes.io/bl...

JerryWang_SAP
24分钟前
0
0
2天闭门培训|以太坊智能合约从入门到实战(北京)

2天培训 16个课时 探寻技术原理,精通以太坊智能合约开发 以太坊智能合约是现在应用的最广泛的区块链应用开发方式,HiBlock区块链社区针对以太坊智能合约的学习特别推出2天闭门研修班,通过2...

HiBlock
27分钟前
0
0
限定某个目录禁止解析php,限制user_agent,php相关配置

11月20日任务 11.28 限定某个目录禁止解析php 11.29 限制user_agent 11.30/11.31 php相关配置 1.限定某个目录禁止解析php 核心配置文件内容 <Directory /data/wwwroot/www.123.com/upload> p...

hhpuppy
38分钟前
2
0
Spring的好文章

孤傲苍狼 https://www.cnblogs.com/xdp-gacl/p/4249939.html 跟我学spring http://jinnianshilongnian.iteye.com/blog/1413846 SpringIoc 和Spring Aop 代理模式: 静态代理 动态代理 cglib代......

wangwei2134
49分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部