题目:
设计一个运行时间为O(nlogn)算法,给定n个整数的集合S和另一个整数x,该算法能确定S中是否存在两个和相加刚好为x 的元素。
思想:
O(nlogn)+O(n)=O(nlogn);
O(nlogn)就是快排的时间复杂度,O(n)就是查找的时间复杂度。
快排自然不必过多的赘述。它的平均复杂度就是O(nlogn)亲测好用!
查找:
对于一个有序的数组,我们只需要设置两个变量,从两边往中间夹逼即可。
例如:
2 3 4 5 9 10 13 (n=7,x=8,i=0,j=6)
si=2,sj=13,2+13=15>x=8;
故:j--;
si=2,sj=10,2+10>x=8;
当i=0,j=3,si=1,sj=5,si+sj=7<x=8;
故:i++;
以此类推,直到i=1,si=3,j=3,sj=5,si+sj=x;
然后退出循环即可。
这里存在可能找不到元素,故我们最开始的循环条件就是while(i<j),否则退出。