【原】位图实现1亿个数找重复值

/ 0评 / 1

场景:1亿个数字中有2个相同的,怎么找?

分析:面对此问题要学会分析题目的真实用意,如果说用“暴力破解”去跑那必然可解,但绝对不是题目所想要的结果。尤其是在面试的过程中,要懂得去理解面试官问题的真实意图和想要的答案,否则答非所问或者跑题,必然很难留下好印象。

面对此类问题,通常想要的一定是资源消耗较小,时间较快的方法,即快速、时间和空间最优。下面是几个常见的方法:

个人认为位图是一个比较合适的方法,下面我也将使用位图来模拟一下这个场景。使用Go语言编写。

package main

import (
	"fmt"
)

func main() {
	//我们模拟产生1 - 1亿,来做实验
	maxnum := 100000000 //设置最大值
	//模拟产生1亿个数
	bif := make([]uint,maxnum)
	for i := 0 ; i< maxnum; i++ {
		bif[i] = uint(i)
	}
	//假设一个重复数
	bif[9999998] = 1007
	//创建最大值是1以的位图
	bit := NewBitMap(maxnum)
	for _,v := range bif{
		//判断是否存在
		if bit.IsExist(v) {
			fmt.Println("找到重复数:",v)
			return
		}
		//将不存在的数,添加到BitMap里
		bit.Add(v)
	}
}


//位图
type BitMap struct {
	bits []byte
	//这样写的目的是便于扩展 一些其它参数,如最大值、最小值、长度等
	//max int
	//min int
	//len int
	// ......
}

//初始化一个BitMap
//一个byte有8位,代表8个数字,取余后加1便是存放最大数所需的容量
func NewBitMap(max int) *BitMap {
	bits := make([]byte, (max>>3)+1)
	return &BitMap{bits: bits}
}

//添加一个数字到BitMap
//计算添加数字在数组中的索引index,一个索引可以存放8个数字
//计算存放到索引下的第几个位置,一共0-7个位置
//原索引下的内容与1左移到指定位置后做或运算
func (b *BitMap) Add(num uint) {
	index := num >> 3
	pos := num & 0x07
	b.bits[index] |= 1 << pos
}

//判断一个数字是否存在
//找到数字所在的位置,然后做与运算
func (b *BitMap) IsExist(num uint) bool {
	index := num >> 3
	pos := num & 0x07
	return b.bits[index]&(1<<pos) != 0
}

其实最近确实多次用到位图去解决问题,所以更倾向于优先使用位图来解决问题。

你是否还有更好的方案去解决此类问题呢?请在评论区留言~~~