Группировка элементов в массиве?

Question

Эй, ребята, если у меня есть массив, который выглядит как [A, B, C, A, B, C, A, C, B] (случайный порядок), и я хочу расположить его в [A, A, A, B, B, B, C, C, C] (каждая группа находится вместе), и допускаются только следующие операции: 1) запросить i-й элемент массива 2) поменять местами два элемента в массиве.

Как разработать алгоритм, который выполняет работу в O (n)?

Спасибо!

Answer 1

Это на самом деле просто сортировка по счету .

Сканируйте массив один раз, посчитайте количество As, Bs, Cs - которые должны дать вам представление. Это похоже на bucket sort - не совсем, но в том же духе. Подсчет As Bs и Cs должен дать вам представление о том, где находится строка As, Bs и Cs.

Answer 2

Алгоритмы сортировки - это уже не то, что вы разрабатываете заново (т. Е. Первый шаг процесса разработки); Вам следует изучить известные сортировка алгоритмы и посмотреть, что соответствует вашим потребностям.

(Конечно, возможно, вам действительно потребуется собственный новый алгоритм сортировки, но обычно он отличается & mdash; и весьма специфичен & mdash; требованиям .)

Если это не ваш первый шаг (но я не думаю, что это так), было бы полезно узнать, что вы уже пробовали и как это вам не удалось.