快速sort一个字符串 && 快速寻找子串 Sort a list of string and search for a substring in a string
1. 快速sort一个list,list里面的元素都是string
eg: ["ab","is","cs","iw"]
我们需要每一位每一位的比较,如果使用quick sort对每一位来排序,复杂度太高了。
首先介绍:key-indexed counting:(0(n))时间
首先得到出现的字母的频率,按照字母顺序来存储
然后将count[i+1] = count[i] + count[i+1]
这样每一个元素代表之前一共有多少个数值。
那么一个字母的正确排列位置应该在count[i] 到count[i+1]之间
这样就可以在o(2n)的时间内排列好字符
接下来对一个长度大于一的字符串"cdxa"
我们从右往左(LSD radix sort),从左往右(MSD radix sort),3分(3-way radix sort)
LSD(从右往左对基于每一位,对所有的字符进行排队)
MSD 从左到右,排序后partition,递归的对每一个partition执行
3-way quick-sort
将第一个数作为基准,比它小的分一组,跟它一样大的分一组,比它大的分一组。
在一个数组中寻找一个子串
除了一个长度为k的窗口一位一位去试,还有更好的方法:
将target从左往右移动,但对比的时候从target的右边向左边对比,当不匹配时skip:
1.如果遇到的string的值不属于target,则直接跳到这个值的右边。
2.如果遇到的string的值属于target,则将target中最右边的这个值与它对其
如果回退了,则我们将target向右移动一位,而不选择回退