使用位图法(bitmap),判断整数是否重复出现
作者:bin使用位图法,记录海量签到数据,打卡数据。
package com; /** * 题目:2.5亿个数字如何判断数字是否重复出现。 * * 解体思路: * 使用位图法,占位表示数字重复出现, * 一个int等于4个字节,1个字节8位,所以一个int可以表示32个数字。 * 大于32使用数组存,每组32个数字。 * 同时,题目要求表示重复出现,如果只用1个状态位,即只有0、1无法表示3状态(不存在、存在、重复), * 即可以将状态位扩展到2位,就可以支持4种状态情况,00、01、10、11, * 相应的。将数组变成存16个即可。 */ public class SpringBin { public static void main(String[] args) { setBit(100); setBit(101); setBit(102); setBit(100); System.out.println(getBit(100)); } /** * 定义位图 * 当前一位存放16个数字,假设数组长度为10,那么可以存放10 * 16 = 160个不同的数字. * 16000000即可以存放,16000000*16个数字。 */ static int[] bitmap = new int[16000000]; /** * 1 1-2 00000000 00000011 * 2 3-4 00000000 00001100 * 3 5-6 00000000 00110000 * 4 7-8 00000000 11000000 * 5... * * 根据规律推导出公式: * (1 << (column * 2)) 表示 10 * (1 << (column * 2 - 1)) 表示 01 * @param data */ public static void setBit(int data){ int row = row(data); int column = column(data); if (getBit(data)) { //(1 << (column * 2)) 表示设置01 bitmap[row] = bitmap[row] | (1 << (column * 2 - 1)); }else { //(1 << (column * 2 - 1)) 表示设置10 bitmap[row] = bitmap[row] | (1 << (column * 2)); } } private static int row(int data){ return data / 16; } private static int column(int data){ return data % 16; } public static boolean getBit(int data){ int row = row(data); int column = column(data); /** * 同理用公式判断是否存在10,存在重复 */ if ((bitmap[row] & 1 << (column * 2 - 1)) == 1 << (column * 2 - 1)){ System.out.println(data + "重复key"); return true; } /** * 同理用公式判断是否存在01,存在key */ if ((bitmap[row] & 1 << (column * 2)) == 1 << (column * 2) ){ System.out.println(data + "唯一key"); return true; } System.out.println(data + "key不存在"); return false; } }