首先,通过归并排序,对数组进行排序(因为后面用到的二分查找需要顺序表。并且题目只要求确认是否存在,并没有要求返回对应index,所以在一开始进行排序操作)。
外层通过循环,依次获得对应元素,根据branchTarget = target - array[i]这样的操作获得两个元素中的另一个元素。再通过二分查找,判断集合中是否存在对应的另一个元素。
归并排序的时间复杂度为nlgn,循环遍历的时间复杂度为n,二分查找的时间复杂度为lgn,所以最终的耗时为nlgn+n*lgn,故最终时间复杂度为nlgn。
具体实现,请看本章代码实现博客。
思考由于该章的思考题,都需要进行公式计算与展示,而我并不会用MarkDown表示,所以就不写出来了。如果感兴趣,给各位一个资料(Algorithems Solutions)。
总结其实这个章节还是比较简单的。算法上面举了一些有关排序的例子,以及一个折半查找的demo。数学方面,一方面需要还记得高中的数学归纳法,另一方面需要一定的排列组合的认识(进行复杂度的计算表)。
附录 参考《算法导论》
Algorithems Solutions