zealic
2019-03-25 00:55:34 +08:00
详细说下我在一楼说的算法
(Bitmap + 二叉树) x 链表
空间最小化，根据已知条件，最坏的情况下内存占用为 645K，计算量也不大
算法细节为，
BitmapBinaryTree，六级，1->2-4->8->16->32
然后循环所有 ID,每个 ID 置位 Bitmap，发现重复的 ID 就创建一个新的 BitmapBinaryTree 并置位
如此循环最多创建 10000 个 BitmapBinaryTree
因为大多数 ID 不重复，大部分数据位只会存在于第一个 BitmapBinaryTree
那么最终数据结构应该叫做 BinaryTreeChain，数据结构如下
type BinaryTreeChain struct {
Left *Bitmap128
Right *Bitmap128
Next *BinaryTreeChain
// 二分查找对应的 Bitmap8 并置位，若设置成功返回，否则代表重复
// 重复需要创建或查找 Next 链并置位
SetByID(id int256) bool
//获取值
GetByID(id int256) bool
// 计算总数
CountByID(id int256) bool
}
type Bitmap128 struct {
Left *Bitmap64
Right *Bitmap64
}
type Bitmap64 struct {
Left *Bitmap32
Right *Bitmap32
}
type Bitmap32 struct {
Left *Bitmap16
Right *Bitmap16
}
type Bitmap16 struct {
Left *Bitmap8
Right *Bitmap8
}
type Bitmap8 = byte