【扩展】求m个排好序的数组中,第k小的。
前面有dreamhunter_lan网友提出的问题
http://topic.csdn.net/u/20110614/21/caa44fc3-758b-42f9-9a5d-110b68292b84.html
现在扩展一下:
设m个数组已经从小到大排好序,每个数组的长度分别为N1、N2、N3……Nm
1> 如果数据有重复,求第k小的数。
2> 如果数据不重复,求第k小的数。(是否有更快的方法)
http://topic.csdn.net/u/20110614/21/caa44fc3-758b-42f9-9a5d-110b68292b84.html
现在扩展一下:
设m个数组已经从小到大排好序,每个数组的长度分别为N1、N2、N3……Nm
1> 如果数据有重复,求第k小的数。
2> 如果数据不重复,求第k小的数。(是否有更快的方法)
作者: gogdizzy 发布时间: 2011-06-16
我感觉,这个问题要看k的大小和数组的个数,如果k要是很小或是很大,用归并就比较合适(很大的话转换成找第m-k大的数)。如果k在m个数的中间位置,并且数组数不是很多的话,做剪枝后再查找比较好。
作者: elated 发布时间: 2011-06-16