算法基础练习 最小的k个数+扩展大数据

Reply Share

题目描述：
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。

问题分析：

最简单的思路应该是对数据进行排序，排序后得到的前k个数字就是要求的数据。这种思路的时间复杂度为O(nlogn)。
如果能修改数组中的数字，可以参考快速排序中的方法，选取第k个数作为参考，将比它小的数字全部放在左侧，比它大的数字全放在右侧。那么左侧的k个数字就是最终的结果数字。这种思路的时间复杂度为O(n)。代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
void GetLeastNumbers(int* input,int n,int* output,int k)
{
    if(input==NULL || output==NULL || k>n || n<=0 || k<=0)
    return;

    int start=0;
    int end=n-1;
    int index=Partition(input,n,start,end);
    while(index!=k-1){
        if(index>k-1){
            end=index-1;
            index=Partition(input,n,start,end);
        }
        else{
            
        }

    }
}

int Partition(int* data,int length,int start,int end){
    if(data==NULL || length<=0 || start<0 || end>=length)
        throw new std::exception("Invalid Parameters");
    int index=RandomInRange(start,end);
    Swap(&data[index],&data[end]);

    int small=start-1;
    for(index=start;index<end;++index)
    {
        if(data[index]<data[end]){
            ++small;
            if(small!=index)
                Swap(&data[index],&data[small]);
        }
    }
    ++small;
    Swap(&data[small],&data[end]);

    return small;
}

这种思路是有一定限制条件的。我们需要修改输入的数组，因为函数Partition会调整数组中的数字的顺序。

思路二：

我们可以先创建一个大小为k的数据容器来储存最小的k个数字，接下来我们每次从输入的n个整数中读入一个数。1）如果容器中已有的数字少于k个，则直接把这次读入的整数放入容器之中；2）如果容器中已有k个数字，也就是容器已满，此时我们不能直接插入数字。我们找出容器中k个数字的最大值，然后和这次待插入的整数进行比较。3）如果待插入的值比已有的最大值小，则用这次插入的数据替换当前已有的最大值；4）如果待插入的值比已有的最大值大，则直接丢弃。最后容器中的k个数即为最终要求的结果。
因此当容器满了之后，我们要做三件事：一是在k个整数中找到最大数；二是有可能删除容器中的最大数；三是有可能要插入一个新的数据。用二叉树的结构来考虑，实现找出n个数据中最小的k个，时间复杂度为O(nlogk)。
红黑树 是一种自平衡的二叉树结构，红黑树通过把节点分为红黑两种颜色并根据一些规则确保树在一定程度上是平衡的，从而保证在红黑树中查找、删除和插入操作都只需要O(logk)时间。STL中set和multiset都是基于红黑树实现的。利用set和multiset可以实现题目要求
的查找。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
typedef multiset<int,greater<int>>            intSet;
typedef multiset<int,greater<int>>::interator setIterator;

void GetLeastNumbers(const vector<int>& data,intSet& leastNumbers,int k){
    leastNumbers.clear();

    if(k<1 || data.size()<k)
        return ;

    vector<int>::const_iterator iter=data.begin();
    for(;iter!=data.end();++iter){
        if(leastNumbers.size()<k)       //容器未满
            leastNumbers.insert(*iter);
        else{
            setIterator iterGreatest=leastNumbers.begin();
            if(*iter<*(leastNumbers.begin())){      //待插入的数较小
                leastNumbers.erase(iterGreatest);   //删除容器中最大的一个值
                leastNumbers.insert(*iter);  //将待插入的数加到容器中
            }
        }
    }
}

对比分析

基于函数Partition的方法时间复杂度O(n),比后者思路要快，但同时也有限制，比如会修改数组中的数据。
后者的解法思路虽稍慢一点，但有两个优点。一是没有修改输入的数据。二是它比较适合海量的数据的输入。

1