现在的位置: 首页 > 综合 > 正文

One编程组第六次题目

2013年07月06日 ⁄ 综合 ⁄ 共 874字 ⁄ 字号 评论关闭
 

将无序的数组成的一个集合S,分成两个值相等的集合AB。(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)

抱歉!评论已关闭.