[编程技术] 两组ID对应一组ID，有没有O(1)的算法

发信人: moudy (moudy), 信区: Programming
标 题: 两组ID对应一组ID，有没有O(1)的算法
发信站: 水木社区 (Sat Mar 31 17:22:14 2018), 站内

假设
有目录IdA：0, 1, 2, 3, 4
有品类IdB：0, 1, 2, 3, 4

IdA和IdB组合后的子集，产生实际可售商品编组IdC： 0， 1， 2， 3， 4， 5， 6， 7， 8， 9
比如：
IdC(0)=(IdA(0), IdB(0))
IdC(1)=(IdA(0), IdB(2))
IdC(2)=(IdA(1), IdB(1))
IdC(3)=(IdA(2), IdB(3))
IdC(4)=(IdA(2), IdB(4))
IdC(5)=(IdA(3), IdB(0))
IdC(6)=(IdA(3), IdB(1))
IdC(7)=(IdA(3), IdB(2))
IdC(8)=(IdA(3), IdB(3))
IdC(9)=(IdA(4), IdB(4))

现在要根据IdA和IdB找出对应的IdC
目前我能想到的最好的解决方案是
- IdC按照 IdA主序，IdB做第二序 排序后生成一个列表。 索引是IdC，存的值是IdB
上面例子得出的 IdCList = { 0， 2，1, 3, 4, 0, 1, 2, 3, 4 }
- IdA生成一个索引表 struct IdARange { int IdCStart, IdCEnd }, 记录IdC列表里子表的起终位置
上面例子得出的 IdARangeList = { (0,1), (2,2), (3,4), (5,8)， （9,9） }
- 查询时先用IdA找出IdARange，再用二分查找找出IdB的值，然后索引就是IdC

这样存储复杂度是O(N)， 查询复杂度是O（logN）

有没有更NB的办法实现存储O(N) 时间O（1）的查询呢？
--
※ 修改:·moudy 于 Mar 31 17:39:29 2018 修改本文·[FROM: 213.95.148.*]
※ 来源:·水木社区 http://m.newsmth.net·[FROM: 213.95.148.*]


from 水木社区 电脑技术区十大热门话题 https://ift.tt/2pWOxUP
via IFTTT