学步园

    某笔试题:内存中有一个长数组,有100W条记录, 每个记录为一个struct array, sizeof( array ) = 512, 在这个struct里有一个int型成员变量weight, 现要取得按个weight值从大到小排序的前500个数组单元(求N里的前K个大的数)

直接贴代码吧,废话少讲(先说方法吧)~~~~解释在注释里:)

const static long N = 10000000; 
const static long K = 100;
static long cnt;

struct Elem
{
 Elem()
 {
  weight = rand()%100000;
 }
 long weight;
 //char data[512];
};

void main()
{
 srand(time(NULL));

 //直接用数据会越过程序初始栈大小,所在要在堆里申请空间~~~运行时可以断一下点,看一下任务管理器占用多少内存
 Elem  * p = new Elem[N];
 long take = GetTickCount();  
 //time_t   first,   second; 
 //first   =   time(NULL);     /*   Gets   system */

 //方法一
 //先将最大的k个交换到前面,再对其全排
 DirectSearch( p, K );
 QuickSort( p, 0, K - 1 );
 PrintElem( p, K );

 //方法二
 //先用半快排,求出长度为k的区间后,再对其全排
//  PartQuickSort( p, 0, N - 1, K );
//  QuickSort( p, 0, K - 1 );
//  PrintElem( p, K );

 //方法三
 //用一个小根堆保存这k个数, 遍历一次即可,每次与第一个比较, 如果更新了就调整
 //HeapK( p, K );
 
 //估计做出以上三种方法的实现,面试官都基本满意啦,一般软件公司的offer也是八九不离十了.
 //但是,继续还有方法...

 //解法四: 如果加上限制条件(1) 所有数为整数 (2) 所有数的变化范围不大 这样就可以利用记数排序法的思想
 //Countsort( p, K )
 
 //second   =   time(NULL);   /*   Gets   system   time    again   */
 cout<<"tick="<< GetTickCount() - take <<endl;
 cout<<"count="<< cnt <<endl;

 //cout<<"tick="<< difftime(second,first)<<endl;  
 
 delete p;
}

下面者是实现~~~

//解法一: 直接查找 O( N*k), 其实当 k < log2(N) 时是可以用的, 因为要完全排序需要 O( n* log2(n) )<br /> //但是如果要求k个数排序的话,还要至少加上 k*log2(k)的时间<br /> //直接将其交换到前面位置<br /> void DirectSearch( Elem * src, int k )<br /> {</p> <p> long i =0, j, l,idx;</p> <p> long max;<br /> Elem t;<br /> for( l=0; l<K; l++ )<br /> {<br /> max = src[l].weight;<br /> for( j=l; j <N; j++)<br /> {<br /> if( max < src[j].weight )<br /> {<br /> max = src[j].weight;<br /> idx = j;<br /> }</p> <p> //计数器<br /> ++cnt;<br /> }</p> <p> //交换到前面<br /> memcpy( &t, &src[idx], sizeof(Elem) );<br /> memcpy( &src[idx], &src[l], sizeof(Elem) );<br /> memcpy( &src[l], &t, sizeof(Elem) );</p> <p> }</p> <p>}</p> <p>//解法二: 部分快排</p> <p>//前置声明<br /> int PartPartion( Elem * src, int start, int end );</p> <p>//部分快排,实现将前K个最大的放在前端(N个无素无序)<br /> //完成后前k个最大数将会放在数组的前k的位置,无序<br /> void PartQuickSort( Elem * src, int start , int end, int k )<br /> {<br /> //按照快排的思想,以第一个为标记元素M,大于M的放交换到左边,小于M放到右边, 当左分区的要少于N时结束<br /> //返回上一次分区的大小<br /> //---------------<br /> //其实上面的想法，会导致分组过大的，如要在10个里找出前5个，当计算到m为3时，但前一个可能为8，<br /> //这里就直接全排这个8个元素就会做很我多无用的排序了<br /> //优化:<br /> //(1) 当找到 m < N 时, 继续在大的分区找出 N - m个<br /> //(2)递归进行,真到有m == N 时结束<br /> //(3)<span class='wp_keywordlink'><a href="http://www.xuebuyuan.com/category/%E7%AE%97%E6%B3%95" title="算法" target="_blank">算法</a></span>复杂度为O(N* log2(k) )</p> <p> //if( k == 0 )<br /> //return;</p> <p> int m = 0;<br /> //m = PartPartion( src, cur , ElemLen - 1 );<br /> //if( m <= k )<br /> //PartQuickSort( src + m + 1, ElemLen - m -1 , k - m - 1, m + 1);</p> <p> if( start < end )<br /> {<br /> m = PartPartion( src, start , end );</p> <p> if( m <= k )<br /> PartQuickSort( src, m+1 , end, k - m + 1 );<br /> else<br /> PartQuickSort( src, start , m - 1, k );</p> <p> }</p> <p>}<br /> //部分快排的分解<br /> int PartPartion( Elem * src, int start, int end )<br /> {<br /> Elem t, mid;</p> <p> int i,j;</p> <p> i = start;<br /> j = end;<br /> mid = src[start];</p> <p> while( i< j )<br /> {<br /> while( i<j && src[j].weight <= mid.weight )<br /> j--;</p> <p> while( i < j && src[i].weight >= mid.weight )<br /> i++;</p> <p> if( i<j)<br /> {<br /> //如果Elem结构里有数组,就不能直接赋值,所以改用memcpy直接复制内存<br /> memcpy( &t, &src[i], sizeof(Elem) );<br /> memcpy( &src[i], &src[j], sizeof(Elem) );<br /> memcpy( &src[j], &t, sizeof(Elem) );<br /> }<br /> }</p> <p> memcpy( &t, &src[i], sizeof(Elem) );<br /> memcpy( &src[i], &src[start], sizeof(Elem) );<br /> memcpy( &src[start], &t, sizeof(Elem) );<br /> ++cnt;</p> <p> return i;<br /> }<br /> //对前N个元素进行快排<br /> void QuickSort( Elem * src, int start , int end )<br /> {<br /> //完全排序<br /> if( start < end )<br /> {<br /> int m = PartPartion( src, start , end );<br /> QuickSort( src, start, m -1 );<br /> QuickSort( src, m +1, end );<br /> }<br /> }</p> <p>//解法三: 将一个K个数据的堆,遍历一次即可,以最小堆形式,这样只要比较第一个元素F, 如果比F大,就替找F,之后调整堆<br /> //同样算法复杂度为 O(N* log2(k) ), 而且实现简单</p> <p>//前置声明<br /> bool AdjHeap( int * WArray, int i, int len );<br /> void MinHeap( int * WArray, int len );<br /> void HeapSort( int * WArray, int len );</p> <p>void HeapK( Elem * src, int k )<br /> {<br /> //所有元素以一个数组表示, 再按堆操作调整<br /> //这里只保存weight值<br /> int * weight = new int[ k ];<br /> memset( weight, 0, k );</p> <p> long i;<br /> int idx = 0;</p> <p> //先将前k 个元素的weight加入到堆中<br /> for( i=0; i<k; i++ )<br /> weight[i] = src[i].weight;</p> <p> //调整为小根堆,方便比较<br /> MinHeap( weight, k );</p> <p> //遍历一次即可<br /> for( i=k; i<N; i++ )<br /> {<br /> if( weight[0] < src[k].weight )<br /> {</p> <p> //每置换一次堆顶就要重新调整<br /> weight[0] = src[k].weight;<br /> AdjHeap( weight, 0, k - 1 );</p> <p> }<br /> }</p> <p> //最后weight数组为前k个最大的元素,如果要排序输出,那么要做一次堆排序<br /> HeapSort( weight, k );</p> <p> for( i=0; i<K; i++ )<br /> cout<< weight[i] << " ";<br /> cout<<endl;</p> <p> delete weight;<br /> }</p> <p>void HeapSort( int * WArray, int len )<br /> {<br /> int i;<br /> int t;<br /> for( i=0; i<len ; i++ )<br /> {</p> <p> t = WArray[0];<br /> WArray[0] = WArray[len - i -1];<br /> WArray[len - i - 1] = t;</p> <p> //当没有调整时,完成排序<br /> AdjHeap( WArray, 0, len - i - 2 );</p> <p> }<br /> }</p> <p>bool AdjHeap( int * WArray, int i, int len )<br /> {<br /> bool change = false;<br /> int j,t;<br /> for( j =i*2+1; j <= len; j = j*2+1 )<br /> {</p> <p> if( j +1 <= len && WArray[j] > WArray[ j +1 ] )<br /> j++;</p> <p> if( WArray[j] < WArray[(j-1)/2] )<br /> {<br /> change = true;<br /> t = WArray[(j-1)/2];<br /> WArray[(j-1)/2] = WArray[j];<br /> WArray[j] = t;<br /> }</p> <p> }</p> <p> return change;<br /> }</p> <p>void MinHeap( int * WArray, int len )<br /> {<br /> if( len <= 0 )<br /> return;</p> <p> //根据堆的性质: 左孩子为 2i +1 , 右孩为 2i + 2( 因为从0开始计数 )</p> <p> int i;</p> <p> //从最后一个有孩子的结点开始,向前调整<br /> len--;<br /> for( i = (len-1)/2; i >=0; i-- )<br /> AdjHeap( WArray, i, len );</p> <p>}</p> <p>//解法四: 如果加上限制条件(1) 所有数为整数 (2) 所有数的变化范围不大 这样就可以利用记数排序法的思想<br /> //遍历一次N, 找出最大值MAX<br /> //开一个数组 T[MAX];<br /> //再遍历一次N, 对每个数计数 T[ A[i] ]++; ( 0<= i <= N )<br /> //由于是求前K个最大的数,所以就可以从后面起取</p> <p>void Countsort( Elem * src, int k )<br /> {<br /> long i,j;<br /> int max;<br /> int wt;<br /> int * kArray = new int[k];<br /> long take = GetTickCount();<br /> //遍历一次N, 找出最大值MAX<br /> max = src[0].weight;<br /> for( i=0; i<N; i++)<br /> {<br /> wt = src[i].weight;<br /> max < wt ? max = wt:max;<br /> }<br /> //开一个数组 T[MAX];<br /> int * T = new int[ max + 1 ];<br /> memset( T, 0, sizeof(int)*(max + 1) );<br /> //再遍历一次N, 对每个数计数 T[ A[i] ]++; ( 0<= i <= N )<br /> for( i=0; i<N; i++)<br /> {<br /> wt = src[i].weight;<br /> T[ wt ]++;<br /> }</p> <p> //由于是求前K个最大的数,所以就可以从后面起取<br /> int n = k;<br /> int idx = 0;<br /> for( i = max; i>0 ; i-- )<br /> {<br /> //跳过没有的数<br /> if( !T[i] )<br /> continue;<br /> if( T[i] >= n )<br /> {<br /> //保存结果在另一个数组，以免影响计算时间<br /> for( j =0; j<n; j++ )<br /> {<br /> kArray[idx++] = i;<br /> //cout<<i<<" ";<br /> }<br /> break;<br /> }<br /> else<br /> {<br /> //输出这么多个计数<br /> for( j =0; j<T[i]; j++ )<br /> {<br /> kArray[idx++] = i;<br /> //cout<<i<<" ";<br /> }<br /> n -= T[i];<br /> }<br /> }<br /> //输出结果<br /> for( j =0; j<n; j++ )<br /> cout<<kArray[i]<<" ";<br /> cout<<endl;<br /> cout<<"tick="<< GetTickCount() - take <<endl;<br /> delete T;<br /> delete kArray;<br /> }</p> <p>//输出<br /> void PrintElem( Elem * src, int Len )<br /> {<br /> for( int i =0; i< Len; i++ )<br /> cout<<src[i].weight<<" ";<br /> cout<<endl;<br /> }

    呵呵,相信在面试时能详细说出以上几钟算法的优缺点,并现场写出一两个,估计他会当场拍板:我找的就是你!

呼~~~当时就是衰在这个上啦, 所以决定完整的做一遍, 基础还是很重要的!!大家也加油啦~~~