给定一个未排序的数组，例如 9 4 4 9 2 2，我需要一个高效的算法，让我能够在该数组排序时知道该数组中每个数字的起始位置和结束位置。例如，对于上面的数组，数字 2 的起始索引为 0，结束索引为 1。数字 4 的起始索引为 2，结束索引为 3，数字 9 的起始索引为索引为 4，结束索引为 5(排序时)。任何人都知道如何以有效的方式做到这一点？有没有一种方法可以不先对数组进行排序？
最佳答案
您可以利用只有十个不同元素这一事实。
首先，遍历数组一次，计算零、一、二等。
根据这些计数，您可以轻松计算出排序数组中每个数字的起始和结束位置。
这是 Counting Sort 的变体, 除了我们实际上没有填充排序数组。
关于c++ - 开始和结束数组索引算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/15886400/