不舍编码:最小的k个数

    2015年07月04日 Cpp Cpp 字数:4277

这两天看《剑指offer》一书第30题碰到的一道题目:输入n个整数,找出其中最小的n个整数,例如输入4,5,1,6,2,7,3,8这八个数,则其中最小的4个数是1,2,3,4。这道题目之前在面试阿里实习的时候被面试官问道过,当时除了想到罗普大众的排序方法外,没想到其他的好方法。后来面试完自己下面查了一下资料,了解了通过维持一个大小为k的数据容器的方法,还去了解了一下最大堆和最小堆的原理。不过没有具体地去编码,这次练下手,顺带学习一下对set和multiset的认识。

这道题目公认的解法如上面提到的,通过维持一个大小为k的数据容器,在刚开始的时候,先从这n个数里面挑出前k个数放入到数据容器里,假定该容器自带有排序的功能,那么对于剩下的(n-k)个数,我们可以分别将这(n-k)个数与容器中的最大数挨个的进行比较,如果比容器中的最大数要小,则进来,相应的为了始终维持容器中数目为k个,容器中原来最大的就要从容器中移出来。类比一个很简单的例子,比如有一个小黑屋,小黑屋只能容纳k个人,要使这个小黑屋里的人的升高比外面的都是最矮的,那就把黑屋里升高最高的那个作为标杆,比标杆还矮,进来,标杆移除去,重新找标杆,依次循环即可。

上面每次都需要找到k个整数中的最大数,并且在比对的数小于最大数添加进来之前要移除最大数,所以可以采用最大堆。同时还可以用红黑树来实现上述容器,在STL中set,map,multiset,multimap都是基于红黑树(RB-tree)实现的(顺便补充:hashmap,hashset,hashmultiset,hashmultimap是基于hash table)。所以可以采用STL中的multiset来作为该数据容器。

关于set和multiset的区别及用法,STL之五:set/multiset用法详解这篇文章总结得很不错。下面这张图很清楚的给出了set和multiset的区别:

set、multiset都是集合类,差别在与set中不允许有重复元素,multiset中允许有重复元素。 了解了这些,便可以按照按照书上的写出如下解法:

//
//  main.cpp
//  getLeastNumbers
//
//  Created by willard on 15/7/4.
//  Copyright (c) 2015年 wilard. All rights reserved.
//

#include <iostream>
#include <set>
#include <vector>
using namespace std;

typedef multiset<int, greater<int> > itSet;
typedef multiset<int, greater<int> >::iterator setIterator;

void getLeastNumbers(const vector<int> &data, itSet &leastNumbers, int k){
    leastNumbers.clear();
    if(k < 1 || data.size() < k) return;
    for(vector<int>::const_iterator iter = data.begin(); iter != data.end(); iter++){
        if(leastNumbers.size() < k){
            leastNumbers.insert(*iter);
        }else{
            setIterator iterGreatest = leastNumbers.begin();
            if(*iter < *iterGreatest){
                leastNumbers.erase(iterGreatest);
                leastNumbers.insert(*iter);
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    // insert code here...
    std::cout << "Hello, World!\n";

    int A[] = {2, 1, 4, 2, 5, 1, 6, 9, 3, 4};
    vector<int> dataset(A, A+10);
    itSet leastNumbersSet;
    int k = 5;

    getLeastNumbers(dataset, leastNumbersSet, k);

    for(setIterator i = leastNumbersSet.begin(); i != leastNumbersSet.end(); ++i)
        cout<< *i << " ";
    cout << endl;

    return 0;
}

上面在定义multiset是采用的是greater,也就是容器的数据是从大到小排列的,默认是less从小到大排列的。所以在数据容器中寻找最大迭代对象时用的是leastNumbersSet.begin()。其余部分的都极好理解,就酱紫。

comments powered by Disqus