本文共 2574 字，大约阅读时间需要 8 分钟。

【Java面试高频-集合】如何在10亿int型数，统计只出现一次的数字？

10亿int整型数，以及一台可用内存为1GB的机器，时间复杂度要求O(n)，统计只出现一次的数？

分析

首先分析多大的内存能够表示10亿的数呢？一个int型占4字节，10亿就是40亿字节（很明显就是4GB），也就是如果完全读入内存需要占用4GB，而题目只给1GB内存，显然不可能将所有数据读入内存。

我们先不考虑时间复杂度，仅考虑解决问题。那么接下来的思路一般有两种。

1. 位图法：用一个bit位来标识一个int整数。

一种是位图法，如果各位老司机有经验的话很快会想到int整型数是4字节（Byte），也就是32位（bit），如果能用一个bit位来标识一个int整数那么存储空间将大大减少。另一种是分治法，内存有限，我想办法分批读取处理。下面分析一下位图法。

位图法

位图法是基于int型数的表示范围这个概念的，用一个bit位来标识一个int整数，若该位为1，则说明该数出现；**若该为为0，则说明该数没有出现。**一个int整型数占4字节（Byte），也就是32位（bit）。那么把所有int整型数字表示出来需要2^32 bit的空间，换算成字节单位也就是2^32/8 = 2^29 Byte，大约等于512MB

// 插播一个常识2^10 Byte = 1024 Byte = 1KB2^30 Byte = (2^10)^3 Byte = 1024 * 1024 * 1024 Byte = 1GB

这下就好办了，只需要用512MB的内存就能存储所有的int的范围数。

解决方案

那么接下来我们只需要申请一个int数组长度为 int tmp[N/32+1]即可存储完这些数据，其中N代表要进行查找的总数（这里也就是2^32），tmp中的每个元素在内存在占32位可以对应表示十进制数0~31,所以可得到BitMap表:

• tmp[0]:可表示0~31
• tmp[1]:可表示32~63
• tmp[2]可表示64~95
• ~~

假设这10亿int数据为：6,3,8,32,36,……，那么具体的BitMap表示为

(1). 如何判断int数字放在哪一个tmp数组中：将数字直接除以32取整数部分(x/32)，例如：整数8除以32取整等于0，那么8就在tmp[0]上；

(2). 如何确定数字放在32个位中的哪个位：将数字mod32取模(x%32)。上例中我们如何确定8在tmp[0]中的32个位中的哪个位，这种情况直接mod上32就ok，又如整数8，在tmp[0]中的第8 mod上32等于8，那么整数8就在tmp[0]中的第八个bit位（从右边数起）。

然后我们怎么统计只出现一次的数呢？每一个数出现的情况我们可以分为三种：0次、1次、大于1次。也就是说我们需要用2个bit位才能表示每个数的出现情况。此时则三种情况分别对应的bit位表示是：00、01、11

我们顺序扫描这10亿的数，在对应的双bit位上标记该数出现的次数。最后取出所有双bit位为01的int型数就可以了。

自实现的代码

如何确定每个数据在bitmap中的位置

value位于数组bitmap中的index = value/32;

value位于数组bitmap[index]这个int中的 bit位置offset=value%32-1(offset是1移动多少位，位于第六位则需要1移动五位，所以要减一)；

如何对一个int类型的32位为bit的某一个bit进行赋值操作呢？

bitmap[index] = bitmap[index] | 1<

1<<offset即为value的bitmap的位置，与目前有的值进行或操作进行合并

如何对一个int类型的32位为bit的某一个bit进行读取操作？

bitmap[index] >> offset & 0x01 == 0x01?true:false;

如何判重？

设置bit时，先保存前值，设置之后如果值没有发生改变，则说明此bit位之前已经为1，即发生了重复

int temp = a[index];a[index] = a[index] | 1<

如何根据bitmap恢复原始数据？

for(int i=0;i
   
    > j & 0x01 == 0x01?true:false;        if(true){
               int data = i*32 + j+1;        }    }}
   

class BitSet{
   	// 常数	static final int N = 1000000;	// 数组存储	int[] bitMap;	public BitSet(){
   		bitMap = new int[N/32 + 1];	}	// 添加一个数字	public void add(int value) {
   		int index  = value/32; // 位于数组bitmap中的index下标索引值		int offset = value%32-1; //这个int中的bit位置 offset是1移动多少位，位于第六位则需要1移动无位		// 放入值		bitMap[index] = bitMap[index] | 1<
   
    >offset)&0x01)==0x01?true:false;	}		// 如何根据bitmap恢复原始数据	public void reverseDigit() {
   		for(int i=0;i
    
     >j)&0x01) == 0x01?true:false;				if(flag) {
   					int data = i*32+ j+1;				}			}		}	}}
    
   

调用java库的代码

public static void main(String[] args) {
   		int[] array = new int[] {
   1,2,3,22,3};		BitSet bitSet = new BitSet();		// 将数组内容放入bitmap中		for(int i=0;i

转载地址：https://codingchaozhang.blog.csdn.net/article/details/116737047 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！