One编程组第六次题目

将无序的数组成的一个集合 S ，分成两个值相等的集合 A 和 B 。（ A+B=S ）

这个没有好的方法，组合找到一个 A==S/2 即可。

组合相应的算法结构是：

//src 是源数据集合 ,currentIndex 是在源集合里的当前下标 ,length 为源集合的大小 ,dest 是结果集合
,num 是结果集合的元素个数 , 初始化时 , 结果集合要和源集合的个数相等 .
void match( int * src, int currentIndex, int length, int * dest, int
num)
… {
if (currentIndex == length)
return ;

dest[num++] = src[currentIndex++];// 采用当前元素
for ( int i =0 ; i < num; i++)
… {
cout << dest[i]<<" ";
}
cout << endl;
match(src,currentIndex,length,dest,num);// 选用当前元素进行递归
match(src,currentIndex,length,dest,num-1);// 去除当前元素再进行递归
}

无序的数组中找第 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)