若只有4KB内存可用,该如何打印数组中所有重复的元素
若只有4KB内存可用,该如何打印数组中所有重复的元素
一贱书生 发表于1年前
若只有4KB内存可用,该如何打印数组中所有重复的元素
  • 发表于 1年前
  • 阅读 5
  • 收藏 0
  • 点赞 0
  • 评论 0

腾讯云 新注册用户 域名抢购1元起>>>   

/**
 * 功能:给定一个数组,包含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类。

共有 人打赏支持
粉丝 15
博文 722
码字总数 600072
×
一贱书生
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: