数组中最小的n个数

Question

我如何在数组中组装一组最小或最大的数字？例如，如果我想在大小为1000的数组中找到最小的10个数字。

我正在使用C语言，但我不需要特定于语言的答案。我只是试图找出处理这种任务的方法，因为最近经常遇到这种情况。

- piper1935

---

对数组进行排序。 - EOF

http://blog.mischel.com/2011/10/25/when-theory-meets-practice/ - Jim Mischel

Answer 1

快速选择算法允许我们分离出预定义数量的最小和最大数字（无需完全排序）。它使用类似于快速排序算法的划分过程，但当基准元素找到所需位置时即停止。

了解更多

- MBo

---

考虑到使用基数排序对整型数组进行排序的时间复杂度为O(n)，而QuickSelect在最坏情况下的时间复杂度为O(n^2)，我建议使用排序算法。 - EOF

@EOF 一种方法可能取决于条件 - 如果我们不能允许最坏情况的小概率，我们应该选择另一种方法（例如 - 具有 O(nlogk) 复杂度的二进制堆）。请注意，在一般情况下，Q/S 通常是首选排序算法。 - MBo

另一个选择是Introselect，它专门设计用于避免QuickSelect的最坏情况（但如果负担得起，将默认使用QuickSelect）。 - tucuxi

Answer 2

方法1：对数组进行排序

您可以对数组执行类似快速排序的操作，并获取前10个元素。但这样做效率相对较低，因为您只关心前10个元素，而对整个数组进行排序是过度的。

方法2：线性遍历并跟踪10个元素。

int lowerTen = malloc(size_of_array);

//'array' is your array with 1000 elements
for(int i=0; i<size_of_array; i++){
    if(comesUnderLowerTen(array[i], lowerTeb)){
        addTolowerTen(array[i], lowerTen)
    }
}

int comesUnderLowerTen(int num, int *lowerTen){
    //if there are not yet 10 elements in lowerTen, insert.

    //else if 'num' is less than the largest element in lowerTen, insert.
}

void addToLowerTen(int num, int *lowerTen){
    //should make sure that num is inserted at the right place in the array
    //i.e, after inserting 'num' *lowerTen should remain sorted
}

不用说，这不是一个可行的例子。只有当“lowerTen”数组需要维护少量元素的排序列表时才使用此方法。如果您需要在1000个元素的数组中获取前500个元素，则不建议使用此方法。

第三种方法：在填充原始数组时执行第二种方法

只有在逐个填充原始的1000个元素数组时才有效-在这种情况下，您可以在填充原始数组时将“lowerTen”数组作为原始数组进行维护。

第四种方法：不使用数组

如果您可以基于原始数组维护类似于二叉搜索树的数据结构，则此类任务将更容易。但是，构建BST并找到前10个元素与对数组进行排序然后执行相同操作一样好。只有在您的用例要求对真正大型数组进行搜索并且数据需要在内存中时才执行此操作。

- Kevin Martin Jose

---

方法2的一种变体是使用存储在数组中的二进制最大堆来保存最小值（或使用最小堆来保存最大值）。由于二进制最小堆上的操作为O(1)或O(log n)，其中n是要查找的值的数量（而不是数据集大小N），因此这对于n远小于N的情况特别有效。 - Nominal Animal

这一行有一些问题：int lowerTen = (int*)malloc(size_of_array);。1）在C语言中，对返回值进行强制类型转换只会让代码变得混乱。返回类型是 void*，可以赋值给任何其他指针类型。2）malloc() 返回一个指针，而 int lowerTen 是一个整数，不是一个指针。 - user3629249

关于这行代码：for(int i=0; i<array.length; i++){。在 C 语言中，数组没有 .length 属性。 - user3629249

谢谢。我的 C 语言很生疏。我应该提到这是伪代码。已经进行了更正。 - Kevin Martin Jose

Answer 3

实现一个优先队列。 循环遍历所有数字并将它们添加到该队列中。 如果该队列的长度等于10，则开始检查当前数字是否小于该队列中最高的数字。 如果是，则删除该最高数字并添加当前数字。

最终，您将拥有一个包含数组中10个最低数字的优先队列。 所需时间应为O(n)，其中n是数组的长度。

如果需要更多提示，请添加评论 :)

- 5ka

Answer 4

以下是代码：

1. 编译干净
2. 执行所需功能
3. 可能不是最有效的
4. 处理重复项
5. 需要修改以处理小于0的数字

现在，附上代码：

#include <stdlib.h>  // size_t

void selectLowest( int *sourceArray, size_t numItemsInSource, int *lowestDest, size_t numItemsInDest )
{
    size_t maxIndex = 0;
    int    maxValue = 0;

    // initially populate lowestDest array
    for( size_t i=0; i<numItemsInDest; i++ )
    {
        lowestDest[i] = sourceArray[i];
        if( maxValue < sourceArray[i] )
        {
            maxValue = sourceArray[i];
            maxIndex = i;
        }
    }

    // search rest of sourceArray and 
    // if lower than max in lowestDest, 
    // then 
    //    replace
    //    find new max value 
    for( size_t i=numItemsInDest; i<numItemsInSource; i++ )
    {
        if( maxValue > sourceArray[i] )
        {
            lowestDest[maxIndex] = sourceArray[i];

            maxIndex = 0;
            maxValue = 0;
            for( size_t j=0; j<numItemsInDest; j++ )
            {
                if( maxValue < lowestDest[j] )
                {
                    maxValue = lowestDest[j];
                    maxIndex = j;
                }
            }
        }
    }
} // end function: selectLowest

- user3629249