作者：whisper

链接：http://proprogrammar.com:443/article/465

声明：请尊重原作者的劳动，如需转载请注明出处

    很多时候搜索可以和排序结合起来使用以提高效率，看个例子

　　两个集合

　　A = {5，2， 4， 7}

　　B = {5，3，2，1，6，9，7，4}

　　判断A是否是B的子集

　　一般的暴力解法直接用双层循环一个元素一个元素比较，复杂度为n平方

　　可以先排序再判断，排序复杂度为nlogn，再进行比较，如何比较

　　A : 2 4 5 7

　　B : 1 2 3 4 5 6 7 9

　　比较过程如下：

　　A : 2     4     5     7

　　　  ^
　　B : 1     2     3     4    5     6    7     9

　　      ^

　　不同，B小，B取下个元素

　　A : 2    4     5     7

　　　  ^
　　B : 1    2     3    4     5     6    7     9

　　         ^

　　相同，A取下个元素

　　A : 2    4     5     7

　　　       ^
　　B : 1     2    3     4    5    6    7    9

　　            ^

　　A : 2    4     5     7

　　　       ^
　　B : 1     2     3    4    5    6    7    9

　　                   ^

　　A : 2    4     5    7

　　　        ^
　　B : 1     2    3    4     5    6    7     9

　　                       ^

　　相同，A取下个元素

　　A : 2     4    5     7

　　　              ^
　　B : 1    2    3     4     5    6    7     9

　　                       ^

　　A : 2     4     5    7

　　　               ^
　　B : 1    2    3     4    5     6    7    9

　　                             ^

　　相同，A取下个元素

　　A : 2    4     5    7

　　　                     ^
　　B : 1     2    3     4     5    6     7    9

　　                                ^

　　A : 2     4     5     7

　　　                       ^
　　B : 1    2     3     4    5     6     7    9

　　                                     ^

　　A : 2     4    5    7

　　　                     ^
　　B : 1     2    3     4    5     6    7    9

　　                                            ^

　　相同，比较完毕

　　可见，最多只要遍历A和B一遍就可以得出结果

亲爱的读者：有时间可以点赞评论一下