发信人: 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 水木社区 电脑技术区十大热门话题 htt
