我的c++学习笔记(四)——查找第N小的数

本文描述怎样查找某一数据集中第N小的数
主要参考《算法导论》第9章

主要思路是：先从集合中任意抽取一个数作为比较基准，将集合中的所有数都与该基准比较，小于该基准的放入集合B，否则放入集合C。如果B中的元素数量刚好等于n-1，则该基准则为所查找的目标，如果B中的元素数量大于n-1，则在B中递归查找，否则在C中递归查找

因为不需要排序，该算法平均复杂度为O(lgn)

给定集合A[0->x-1]，含有A[0]至A[x-1]共x个元素
FIND_NTH_MIN(A, n)            /* 在集合A中查找第n小的元素 */
 for i=1->x-1
    if A[i]        insert(B, A[i])
    else
        insert(C, A[i])
insert(C, A[0])
/* 现在集合B中的元素都小于A[0] , 集合C大于等于A[0] */
if n-1    FIND_NTH_MIN(B, n)
else if n-1=size(B)
    return A[0]
else
    FIND_NTH_MIN(C, n-size(B))

上面的伪代码存在两个方面的问题

1 FIND_NTH_MIN的每一次递归调用都需要开辟新的内存来存储集合B和C，这样空间浪费未免也太严重了，我们可以直接将小于比较基准的元素直接移到集合A的前半部分，而大于等于比较基准的元素保持不动，这样就可以将B与C占用的内存节约出来了，看伪代码(注意区间表示的区别):

FIND_NTH_MIN(A, begin, end, n)            /* 在集合A的子集[begin, end)中查找第n小的元素*/
 j=1                                    /* 增加一个指示器，范围(begin, j)即上文所讲的“前半部分” */
 for i=1->x-1
    if A[i]        swap(A[i], A[j])
        ++j
 /* 到这里的时候范围(begin, j)内的元素都小于A[begin] */
 --j
 /* 到这里的时候范围(begin, j]内的元素都小于A[begin]，注意与上面的区别 */
 swap(A[begin], A[j])            
 /* 到这里，A[j]之前的元素就完全小于（而不是小于等于）A[begin] 了*/
 if j+1==n
    return A[j]
 else if n    return FIND_NTH_MIN(A, begin, j, n)
 else
    return FIND_NTH_MIN(A, j+1, end, n-j+1)

2 试想一下，如果从集合{0, 1, 2, 3, 4, 5}中查找第6小（即最大）的数，上面的查找是怎样进行的？
第一次调用FIND_NTH_MIN时，生成的B为空集，而C则包括{1, 2, 3, 4, 5}，然后在C中查找第5小的数
第二次调用FIND_NTH_MIN时，生成的B依然为空集，而C则包括{2, 3, 4, 5}，然后在C中查找第4小的数
……
如此循环往复，每一次递归之后，我们都从较大的子集中查找元素，而且这个子集比原来的集合只减少了一个元素
真是够背的
要解决这个问题，我们可以使用一个随机数产生器，随机指定A中某个元素作为比较基准，而不是每次都以A[0](或者A[begin])为比较基准，这样就好多了，总不可能随机指定出来的结果每次都是最小的吧，要是这样的话还学什么算法，直接买彩票去得了

好了，空谈无益，说了这么多，还是抄家伙上阵吧，以下是上述代码的c++实现，没有采用随机数挑选比较基准，但是也没有开辟新内存存储子集

/**********************************************************************
 * filename: findNthMin.h
 *
 * destination: 提供findNthMin函数的接口及定义
 * 直接采用模板的形式
 *
 * findNthMin行为
 * 在集合[begin, end)中查找第nFind小的数据，并返回指向该数据的迭代器
 * 如果nFind>distance(begin, end)，则返回end
 *
 * 注意：begin, end必须为随机迭代器，本函数不负责检查输入合法性
 *
 * version: 1.0
 * author: compass
 * Email: [e-mail]
 * date: 2009年 11月 30日 星期一 16:47:28 CST
 **********************************************************************/

#ifndef __FINDNTHMIN_H__
#define __FINDNTHMIN_H__

#include <algorithm> /* for std::swap() */

template < typename Iter >
Iter findNthMin(const Iter &begin, const Iter &end,
                   size_t nFind)
{
    if( end<=begin ) /* 检查输入集合是否为空集，这里要求其为随机迭代器*/
        return end;
    if( end-begin == 1) /* 递归调用的终止条件 */
        return (1==nFind)?begin:end;

    Iter iter=begin; ++iter;
    Iter iterLow=begin; ++iterLow; /* (begin, iterLow)集合内的数都小于*begin */
    while(iter!=end)
    {
        if(*iter<*begin)
            std::swap(*iter, *iterLow++);
        ++iter;
    }

    /* 到这里的时候共计找到iterLow-begin-1 个小于*begin的数
     * 而且这些都已经被移动到(begin, iterLow)中
     */

    /* 现在将(begin, iterLow)变为[begin, iterLow) */
    --iterLow;
    std::swap(*iterLow, *begin);

    if(iterLow-begin+1 == nFind)
        return iterLow;
    else if(nFind < iterLow-begin+1)
        return findNthMin(begin, iterLow, nFind);
    else
        return findNthMin(++iterLow, end,
                nFind-(iterLow-begin+1) );
}

#endif /* end findNthMin.h */


以下是我写的测试程序，其中n从参数读入，默认为1，数据集合从stdin读入

/**********************************************************************
 * 程序目的：查找给定数据集合中第N小的数
 * 程序运行时间上界：O(lgn)
 *
 * usage: findNthMin n
 * filename: main.cc
 *
 * version: 1.0
 * author: compass
 * Email: [e-mail]
 * date: 2009年 11月 27日 星期五 15:47:17 CST
 **********************************************************************/



#include "findNthMin.h"
#include <cstdlib> /* for EXIT_SUCCESS and atoi() */
#include <iostream>
#include <vector>
#include <iterator>

int main(int argc, char *argv[])
{
    /* read input from std input */
    std::vector<int> iVec;
    std::istream_iterator<int> iIter(std::cin);
    std::istream_iterator<int> eof;
    std::copy( iIter, eof,
            std::back_inserter(iVec));

    /* 默认查找最小的元素 */
    int nFind = 1;
    if(argc>1)
        nFind = atoi(argv[1]); /* 这里没有错误处理 */

    /* check the nFind */
    if ( nFind<1 || nFind>iVec.size() )
    {
        std::cout << "There is only " << iVec.size()
            << " elements in the set.\n"
            << "no " << nFind << "th smallest element exist!"
            << std::endl;
        return 1;
    }

    /* call algorithm to find */
    std::vector<int>::iterator
        iter = findNthMin(iVec.begin(), iVec.end(),
                   nFind);

    /* output to std output */
    std::cout << "The " << nFind << "th element is "
        << *iter << std::endl;

    return EXIT_SUCCESS;
}

上述代码在g++ (Ubuntu 4.4.1-4ubuntu8) 4.4.1 ，kubuntu9.10 发行版(2.6.31-15-generic内核)环境下粗步测试通过