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

Question

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

Answer 1

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

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

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

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