c++ - 开始和结束数组索引算法

Question

给定一个未排序的数组，例如 9 4 4 9 2 2，我需要一个高效的算法，让我能够在该数组排序时知道该数组中每个数字的起始位置和结束位置。例如，对于上面的数组，数字 2 的起始索引为 0，结束索引为 1。数字 4 的起始索引为 2，结束索引为 3，数字 9 的起始索引为索引为 4，结束索引为 5(排序时)。任何人都知道如何以有效的方式做到这一点？有没有一种方法可以不先对数组进行排序？

Answer 1

您可以利用只有十个不同元素这一事实。

首先，遍历数组一次，计算零、一、二等。

根据这些计数，您可以轻松计算出排序数组中每个数字的起始和结束位置。

这是 Counting Sort 的变体, 除了我们实际上没有填充排序数组。