一串首尾相连的珠子(m个),有N种颜色(N《=10),设计一个算法,取出其中一段,
要求包含所有N种颜色,并使长度最短。并分析时间复杂度与空间复杂度。
首先把珠子确定一个起始位置(随机),然后对所有珠子进行编号,从M+1到M+M,然后
构建N个数组,每个数组中存放每种颜色珠子在链子中的位置(按照从小到大顺序),但是因为第1个珠子和最后一个珠子的句子是1,而不是M-1,所以我们假设有三个项链,首位项链,这样每个珠子就有三个位置,把所有这些位置都放到M个数组中去。
找出N个数组中最短的一个数组,穷举所有出现的位置(从M+1到M+M)范围内的,当确定一个位置k时,从其他N-1个数组中用二分查找的方法找出一个和他距离最近的珠子,当然这前提是假设这个颜色的珠子在第一个位置上,
时间复杂度为,M(位置数)*log(M)(查找)*10(分别假设以每种颜色珠子作为起始位置)
3)设计一个系统处理词语搭配问题,比如说 中国 和人民可以搭配,则中国人民人民中国都有效。要求:
1)系统每秒的查询数量可能上千次;
2)词语的数量级为10W;
3)每个词至多可以与1W个词搭配