开始和结束数组索引算法

Question

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

Answer 1

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

首先，迭代这个数组一次，计数零，则偏多，三三两两等

从这些计数，你可以很容易地计算出的起始和每个数字的排序数组中的结束位置。

这是Counting Sort的一个变种，除了我们实际上并没有填充排序后的数组。