在长度为n的列表中找到x个最小的整数

Question

您有一个包含n个整数的列表，您想要其中最小的x个。例如，x_smallest([1, 2, 5, 4, 3], 3)应该返回[1, 2, 3]。

我将投票支持合理范围内的独特运行时，并将为最佳运行时提供绿色勾选。

我将从O(n * x)开始：创建一个长度为x的数组。迭代x次列表，每次取出下一个最小的整数。

编辑：

• 您无法事先知道这些数字的大小。
• 您不关心最终的顺序，只是想要最小的x个。
• 尽管某些方案已经处理此问题，但让我们假设虽然不能保证唯一的列表，但您也不会得到像[1, 1, 1, 1, 1]这样的退化列表。

- Dave Aaron Smith

---

你为什么把问题结构化成一个竞赛的形式？ - Mark Peters

我不知道，似乎这是一个有趣的方法来做到这一点。 - Dave Aaron Smith

最坏情况是O(n * n)或O(n^2)。但你的算法就像一个过早终止的选择排序。 - Bernie Perez

最佳运行时间并不一定是最佳算法复杂度。例如：Aaron建议使用排序的跳表来始终保持最佳x。看起来算法复杂度最好为O(n log x)，但由于跳表通常涉及大的常数因子，因此它也可能不是最快的。 - kriss

Answer 1

您可以在O(n)的时间内找到第k小的元素。 此前在StackOverflow上已经讨论过这个问题。有相对简单的随机算法（例如QuickSelect），其期望运行时间为O(n)，以及更复杂的算法，其最坏情况下的运行时间为O(n)。

给定第k小的元素，您可以遍历整个列表以找到所有小于第k小元素的元素，之后便可结束操作。（假设结果数组不需要排序。）

总体运行时间为O(n)。

- George Eadon

---

这里假设元素是唯一的。如果第k个元素不唯一，选择就会变得更加复杂。您将选择小于第k小的任何元素，然后用第k小的值填充数组的其余部分。我认为复杂度仍然保持不变。 - Mark Peters

如果你想进行一些保持顺序的选择（例如，如果你有复合值并且只比较它们的一部分 - 键，并且仍然关心有效载荷），那么这将变得更加有趣。你仍然可以通过数据块进行一次遍历来完成，从而获得O(kn)（当k≪n时往往趋近于O(n)）。 - Donal Fellows

@Donal，关于保持顺序的观点很好。我会澄清一下，您并不关心顺序，只想要x个最小值。 - Dave Aaron Smith

Answer 2

在跳表中维护x个最高元素的有序列表。遍历数组，对于每个元素，在跳表中找到它应该插入的位置（log x时间）。如果在列表内部，则是迄今为止最小的x个元素之一，因此将其插入，并删除列表末尾的元素。否则不做任何操作。

时间复杂度为O(n*log(x))。

另一种实现方法：在最大堆中维护x个最高元素的集合，将每个新元素与堆顶元素进行比较，仅在新元素小于堆顶元素时弹出并插入新元素。由于与堆顶元素的比较是O(1)，而弹出/插入是O(log x)，因此这也是O(nlog(x))。

- Aaron

---

我可能会使用自平衡二叉搜索树而不是跳表，但除此之外，这就是我选择的方式。 - svick

@svick：跳表的重点在于从头部删除是O(1)的。当然，列表的取向会稍微有所不同，最大值在头部，最小值在尾部而不是反过来。从BST中删除最大值将会是O(log(x))，这不会改变整体复杂度，但肯定会增加更高的常数因子。此外，重新平衡方案本身有时比在列表中重新链接一个节点更复杂。但是，我想知道是否有一种聪明的方法可以用伸展树来实现这一点？ - Brian Gideon

Answer 3

如果数字范围（L）已知，则可以进行修改后的计数排序。

given L, x, input[]
counts <- array[0..L]
for each number in input
    increment counts[number]
next

#populate the output
index <- 0
xIndex <- 0
while xIndex < x and index <= L
   if counts[index] > 0 then
       decrement counts[index]
       output[xIndex] = index
       increment xIndex
   else
       increment index
   end if
loop

这个算法的运行时间为O(n + L)（内存开销为O(L)），如果范围很小（L＜n log n），它将非常有吸引力。

- Mark Peters

---

我会点赞这个。然而，让我澄清一下整数范围是未知的。 - Dave Aaron Smith

如果不知道L的值，你仍然可以在O(n)时间内对列表进行单次遍历以确定L，然后决定是否值得这样做。 - Mark Peters

另一个好点。而且，你已经描述了适当的范围。赞。 - Dave Aaron Smith

Answer 4

将所有n个数字添加到堆中并删除其中的x个。复杂度为O((n + x) log n)。由于x显然小于n，因此复杂度为O(n log n)。

- Mark Peters

---

不需要将所有数字都保存在堆中，只需保存到目前为止的N个最小值即可。让我详细说明一下。使用最大堆。添加一个数字。如果计数> N，则从堆中删除第一个项目。 - Jim Mischel

是的，@Aaron已经很好地涵盖了这个问题，所以我会让这个答案独立于那个问题。 - Mark Peters

Answer 5

def x_smallest(items, x):
    result = sorted(items[:x])
    for i in items[x:]:
        if i < result[-1]:
            result[-1] = i
            j = x - 1
            while j > 0 and result[j] < result[j-1]:
                result[j-1], result[j] = result[j], result[j-1]
                j -= 1
    return result

最坏情况是O(x*n)，但通常会更接近于O(n)。

- Mark Ransom

Answer 6

在Scala中，以及可能其他函数式语言中，这是一个不需要思考的问题：

scala> List (1, 3, 6, 4, 5, 1, 2, 9, 4)  sortWith ( _<_ ) take 5
res18: List[Int] = List(1, 1, 2, 3, 4)

- user unknown

Answer 7

伪代码：

def x_smallest(array<int> arr, int limit)
    array<int> ret = new array[limit]

    ret = {INT_MAX}

    for i in arr
        for j in range(0..limit)
            if (i < ret[j])
                ret[j] = i
            endif
        endfor
    endfor

    return ret
enddef

- Mentalikryst

Answer 8

你可以先排序，然后取前 x 个值吗？

Java：使用快速排序 O(n log n)

import java.util.Arrays;
import java.util.Random;

public class Main {

    public static void main(String[] args) {
        Random random = new Random(); // Random number generator
        int[] list = new int[1000];
        int lenght = 3;

        // Initialize array with positive random values
        for (int i = 0; i < list.length; i++) {
            list[i] = Math.abs(random.nextInt());
        }

        // Solution
        int[] output = findSmallest(list, lenght);

        // Display Results
        for(int x : output)
            System.out.println(x);
    }

    private static int[] findSmallest(int[] list, int lenght) {
        // A tuned quicksort
        Arrays.sort(list);
        // Send back correct lenght
        return Arrays.copyOf(list, lenght);     
    }

}

它非常快。

- Bernie Perez

---

最彻底的低垂果实答案。 - Dave Aaron Smith

Answer 9

    private static int[] x_smallest(int[] input, int x)
    {
        int[] output = new int[x];
        for (int i = 0; i < x; i++) { // O(x)
            output[i] = input[i];
        }

        for (int i = x; i < input.Length; i++) { // + O(n-x)
            int current = input[i];
            int temp;

            for (int j = 0; j < output.Length; j++) { // * O(x)
                if (current < output[j]) {
                    temp = output[j];
                    output[j] = current;
                    current = temp;
                } 
            }
        }

        return output;
    }

观察复杂度： O(x + (n-x) * x) -- 假设x是某个常数，O(n)

- PeterL

Answer 10

使用 splay tree 如何？由于 splay tree 的自适应平衡方法，它为算法的优雅实现提供了独特的方式，并且可以在此后按顺序枚举 x 项。下面是一些伪代码。

public SplayTree GetSmallest(int[] array, int x)
{
  var tree = new SplayTree();
  for (int i = 0; i < array.Length; i++)
  {
    int max = tree.GetLargest();
    if (array[i] < max || tree.Count < x)
    {
      if (tree.Count >= x)
      {
        tree.Remove(max);
      }
      tree.Add(array[i]);
    }
  }
  return tree;
}

GetLargest和Remove操作的平摊复杂度为O(log(n))，但由于最后访问的项目会冒到顶部，所以通常为O(1)。因此，空间复杂度为O(x)，运行时复杂度为O(n*log(x))。如果数组已经排序，则该算法将在升序或降序排序的数组中实现其最佳情况下的复杂度O(n)。但是，非常奇怪或特殊的排序可能会导致O(n^2)的复杂度。你能猜出需要对数组进行什么样的排序才会发生这种情况吗？

- Brian Gideon

---

有趣。我从未听说过伸展树。你是不是想说 if (array[i] < max or tree.Count < x)？按照你的伪代码，如果你首先遇到最小的整数，我相信伸展树永远不会超过一个整数。 - Dave Aaron Smith