如何求出数组中最小

如何求出数组中最小(或者最大)的k个数(least k问题),数组least

  输入n个整数,如何求出其中最小的k个数?

解法1.
当然最直观的思路是将数组排序,然后就可以找出其中最小的k个数了,时间复杂度以快速排序为例,是O(nlogn);

解法2.
借助划分(Partition)的思路,一次划分可以把枢轴使得枢轴左边的元素都比枢轴小,枢轴右边的元素都比枢轴大(可以参考快速排序及STL中的sort算法)。那么可以基于数组的第k个数字来调整,使得比第k个数字小的数字都位于数组的左边,使得比第k个数字大的数字都位于数组的右边。那么调整完毕后,数组中左边的k个数字就是最小的k个数字(这k个数字不一定是排序的)。该解法时间复杂度最低,但需要修改输入的数组,如果要求不能修改输入的数组,那就行不通了。另外该算法也不大适合海量数据处理,因为没办法一次读入内存,只能一次读取一些。

  C++代码如下:

#include "stdafx.h"
#include <set>
#include <vector>
#include <iostream>

using namespace std;
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 pivotkey = data[start];// 记录枢轴关键字
    while (start < end)
    {
        while(start<end && data[end]>=pivotkey) 
            --end;// 找到从end位置开始向前第一个比枢轴小的元素
        data[start] = data[end];// 将找到的比枢轴小的元素放到前边的空闲位置
        while(start<end && data[start]<=pivotkey) 
            ++start;// 找到从start位置开始向后第一个比枢轴大的元素
        data[end] = data[start];// 将找到的比枢轴大的元素放到后边的空闲位置
    }
    data[start] = pivotkey;// 将枢轴放回中间的空闲位置

    return start;
}

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
        {
            start = index + 1;
            index = Partition(input, n, start, end);
        }
    }

    for(int i = 0; i < k; ++i)
        output[i] = input[i];
}

int _tmain(int argc, _TCHAR* argv[])
{
    int data[] = {4, 5, 1, 6, 2, 7, 3, 0, 100, 8, 4, 2, 8, -1};
    int n = 14;
    int k = 4;
    int* output = new int[k];
    GetLeastNumbers(data, n, output, k);

    for (int i=0; i<n; i++)
    {
        printf("%d\t", data[i]);
    }
    printf("\r\n");
    for(int i = 0; i < k; ++ i)
        printf("%d\t", output[i]);
    delete[] output;
    return 0;
}

解法3. 在本地维护好一个大小为k的容器,该容器能够进行自动排序,能够自动排序的容器可以选择STL中的set和multiset,因为它们内部是基于红黑树来实现的,每次插入删除都会进行自动调整。依次读取数组中的一个新元素,与容器中最大的元素做比较,如果小于容器中的最大的元素,则将该最大元素替换,这样循环一遍需要O(n)的复杂度,每次容器进行调整平均是O(logk),这样该算法最终的时间复杂度是O(nlogk)。显而易见,该算法不需要修改原始数据,且适合海量数据处理。

  C++代码如下:

#include "stdafx.h"
#include <set>
#include <vector>
#include <iostream>

using namespace std;
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 pivotkey = data[start];// 记录枢轴关键字
    while (start < end)
    {
        while(start<end && data[end]>=pivotkey) 
            --end;// 找到从end位置开始向前第一个比枢轴小的元素
        data[start] = data[end];// 将找到的比枢轴小的元素放到前边的空闲位置
        while(start<end && data[start]<=pivotkey) 
            ++start;// 找到从start位置开始向后第一个比枢轴大的元素
        data[end] = data[start];// 将找到的比枢轴大的元素放到后边的空闲位置
    }
    data[start] = pivotkey;// 将枢轴放回中间的空闲位置

    return start;
}

typedef multiset<int, greater<int> >            intSet;
typedef multiset<int, greater<int> >::iterator  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);
            }
        }
    }
}

int _tmain(int argc, _TCHAR* argv[])
{
    int data[] = {4, 5, 1, 6, 2, 7, 3, 0, 100, 8, 4, 2, 8, -1};
    int n = 14;
    int k = 4;
    intSet leastNumbers;

    std::vector<int> dataVec(&data[0], &data[14]);// 以迭代器初始化,注意第二个参数end是最后一个元素的下一个位置
    GetLeastNumbers(dataVec, leastNumbers, k);

    for(setIterator iter = leastNumbers.begin(); iter != leastNumbers.end(); ++iter)
        printf("%d\t", *iter);

    return 0;
}

 

k问题),数组least 输入n个整数,如何求出其中最小的k个数? 解法1.
当然最直观的思路是…

相关文章