文档章节

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

一贱书生
 一贱书生
发布于 2016/11/23 09:08
字数 279
阅读 11
收藏 0
点赞 0
评论 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
博文 723
码字总数 600072
作品 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
99%海量数据处理

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

tantexian
01/15
0
0
十道海量数据处理面试题与十个方法大总结

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

吟啸_徐行
2014/04/02
0
2
php 大数据量及海量数据处理算法总结

下面的方法是我对海量数据的处理方法进行了一个一般性的总结,当然这些方法可能并不能完全覆盖所有的问题,但是这样的一些方法也基本可以处理绝大多数遇到的问题。下面的一些问题基本直接来源...

bengozhong
2016/02/26
58
0
11. Java NIO: Non-blocking Server 非阻塞服务器

现在我们已经知道了Java NIO里面那些非阻塞特性是怎么工作的,但是要设计一个非阻塞的服务仍旧比较困难。非阻塞IO相对传统的阻塞IO给开发者带来了更多的挑战。在本节非阻塞服务的讲解中,我们...

逝去的回忆
2016/11/19
32
0
海量数据处理:十道面试题与十个海量数据处理方法总结

1、海量日志数据,提取出某日访问百度次数最多的那个IP。 首先是这一天,并且是访问百度的日志中的IP取出来,逐个写入到一个大文件中。注意到IP是32位的,最多有个2^32个IP。同样可以采用映射...

ahucsxl
2015/10/08
165
0
《海量数据处理常用思路和方法》

最近有点忙,稍微空闲下来,发篇总结贴。 大数据量的问题是很多面试笔试中经常出现的问题,比如baidu google 腾讯 这样的一些涉及到海量数据的公司经常会问到。 下面的方法是我对海量数据的处...

Picasso
2011/09/23
0
0
映射队列(上)

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

UncP
2017/05/12
0
0
搭建模型第一步:你需要预习的NumPy基础都在这了

  选自 Numpy   机器之心编译   参与:Floney、思源      NumPy 是一个为 Python 提供高性能向量、矩阵和高维数据结构的科学计算库。它通过 C 和 Fortran 实现,因此用向量和矩阵建...

机器之心
07/01
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

JAVA知识点随心记

1.Switch case具体的支持类型? Q:支持byte、short、char、int基本类型,枚举类型和String类型(JDK7以上支持),四种基本类型的包装类型也支持,但是原因在于触发了自动拆箱,将包装类型拆成了基本...

勤奋的蚂蚁
7分钟前
0
0
NoSQL

一、NoSQL介绍 NoSQL属于非关系型数据,mysql属于关系型数据库。 对于关系型数据库来说,是需要把数据存储到库、表、行、字段里,查询的时候根据条件一行一行地去匹配,当数据量非常大的时候...

人在艹木中
12分钟前
0
0
第17章MySQL主从配置

mysql安装总结 mysql主从准备工作: 准备两台机器,每台机器安装msyql服务,并启动mysql服务 mysql详细安装 1.首先下载二进制免编译的包,下载到/usr/local/src/目录下 2.解压压缩包 3.解压完...

Linux学习笔记
16分钟前
0
0
Redis高可用及分片集群

一、主从复制 使用异步复制 一个服务器可以有多个从服务器 从服务器也可以有自己的从服务器 复制功能不会阻塞主服务器 可以通过服务功能来上主服务器免于持久化操作,由从服务器去执行持久化...

Java大蜗牛
20分钟前
0
0
前端面试题汇总

最近在复习,准备找工作了,特此总结一下前端的相关知识。 1.获取浏览器URL中查询字符的参数: function getQuery(name){    var reg = new RegExp("(^|&)"+name+"=([^&]*)"(&|$));...

凛冬来袭
54分钟前
0
0
可持续发展的学习道路

与其要求别人,不如提升自己 内心渴望进步 经常做出改变现有模式,不断学习 寻找资源,整合资源,不断熟练这种模式 渠道很重要 先打开新世界的航路

狮子狗
58分钟前
0
0
apollox-lua开源项目 示例codepen2

今天在示例上增加了几个功能, 首先添加js array的标准库。 所有js array的方法目前都支持了。 添加查看code模式。 点击查看code可以看到生成的lua代码。默认web模式需要把标准库连接进来, ...

钟元OSS
今天
0
0
javascript性能优化之避免重复工作

javascript最重要也最根本的性能优化标准之一是避免工作,避免工作又包括两点,第一,不做不必要的工作,第二,不做重复的已经完成的工作。第一部分可以通过代码重构完成,第二部分不做重复的...

老韭菜
今天
0
0
缓存穿透、并发和雪崩那些事

0 题记 缓存穿透、缓存并发和缓存雪崩是常见的由于并发量大而导致的缓存问题,本文讲解其产生原因和解决方案。 缓存穿透通常是由恶意攻击或者无意造成的;缓存并发是由设计不足造成的;缓存雪...

Java填坑之路
今天
1
0
项目jar包管理构建工具---Maven

一、what is Maven? 我们来寻找一下官网,里面介绍了maven到底是什么?下面一句话就有讲解到:Apache Maven is a software project management and comprehension tool. Based on the conc...

一看就喷亏的小猿
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部