将无序的数组成的一个集合S,分成两个值相等的集合A和B。(A+B=S)
这个没有好的方法,组合找到一个A==S/2即可。
组合相应的算法结构是:
无序的数组中找第2大的数
因为只有两个数,所以先设两个变量,然后在数组中找一遍即可
不过效率是找最大数的两倍。
无序的数组中找第K大的数
这个算法讲起来较为复杂。这个从快速排序中得到的结论。
a) 随机在数组中选一个值c,并将此值放到数组末端
b) 从左边遍历数组,找到第一个比c小的值。停下,然后从右边遍历数组,找到第一个比c大的值然后停下。交换两个值所在的位置。直到i==j,交换a[i]与c的位置。
c) 此时c所在的位置为j,那么c就为第j大的数。
d) 如果k > j,那么就在j后面的数组里用相同的方法找。
e) 如果k == j,恭喜找到了
f) 如果k<j,那么就在前面找。
g) 所以算法复杂度为O(klogk)