Рассеять дубликаты в массиве

Ответ 1

Я считаю, что этот простой алгоритм будет работать:

• подсчитывает количество вхождений каждого отдельного элемента.
• создать новый список
• добавить один экземпляр всех элементов, которые встречаются несколько раз в списке ^{_{(порядок внутри каждой группы не имеет значения)}}
• добавить один экземпляр всех уникальных элементов в список
• добавить один экземпляр всех элементов, которые встречаются несколько раз в списке
• добавить один экземпляр всех элементов, которые встречаются более чем в два раза в списке
• добавить один экземпляр всех элементов, которые встречаются более чем в три раза в списке
• ...

Теперь это интуитивно не даст хорошего распространения:
для {1, 1, 1, 1, 2, 3, 4} == > {1, 2, 3, 4, 1, 1, 1}
для {1, 1, 1, 2, 2, 2, 3, 4} == > {1, 2, 3, 4, 1, 2, 1, 2}

Однако, я думаю, что это лучший спрэд, который вы можете получить, учитывая предоставленную функцию подсчета очков. Поскольку показатель дисперсии подсчитывает сумму расстояний вместо квадрата суммы расстояний, вы можете иметь несколько дубликатов близко друг к другу, если у вас есть большой промежуток где-то еще, чтобы компенсировать.

для оценки суммы квадратов-расстояний, проблема становится сложнее. Возможно, вопрос интервью зависит от кандидата, признающего эту слабость в функции подсчета очков?

Ответ 2

В perl

@a=(9,9,9,2,2,2,1,1,1);

затем создайте хеш-таблицу подсчетов разных чисел в списке, например, частотную таблицу

map { $x{$_}++ } @a;

затем повторно просматривайте все найденные ключи с ключами в известном порядке и добавьте соответствующее количество отдельных номеров в выходной список, пока все ключи не будут исчерпаны.

@r=();
$g=1; 
while( $g == 1 ) { 
   $g=0;
   for my $n (sort keys %x) 
      {
      if ($x{$n}>1) {
                    push @r, $n;
                    $x{$n}--;
                    $g=1
                    }
      } 
}

Я уверен, что это может быть адаптировано к любому языку программирования, который поддерживает хеш-таблицы

Ответ 3

код python для алгоритма, предложенный Vorsprung и HugoRune:

from collections import Counter, defaultdict

def max_spread(data):
    cnt = Counter()
    for i in data: cnt[i] += 1

    res, num  = [], list(cnt)
    while len(cnt) > 0:
        for i in num:
            if num[i] > 0:
                res.append(i)
                cnt[i] -= 1
            if cnt[i] == 0: del cnt[i]

    return res

def calc_spread(data):
    d = defaultdict()
    for i, v in enumerate(data):
        d.setdefault(v, []).append(i)

    return sum([max(x) - min(x) for _, x in d.items()])

Ответ 4

Ответ HugoRune использует некоторые преимущества необычной функции подсчета очков, но мы можем на самом деле сделать еще лучше: предположим, что существует четкие не уникальные значения, тогда единственное, что требуется, чтобы оптимальное решение состояло в том, что первые значения d в выводе должны состоять из них в любом порядке, а также последние значения d в выводе должны состоять из этих значений в любом (т.е., возможно, другом) порядке. (Это означает, что все уникальные числа появляются между первым и последним экземпляром каждого не уникального числа.)

Относительный порядок первых копий неединственных чисел не имеет значения, равно как и относительный порядок их последних копий. Предположим, что значения 1 и 2 появляются несколько раз в вход, и что мы создали решение кандидата, удовлетворяющее условию, которое я дал в первом абзаце, который имеет первую копию 1 в позиции я и первую копию 2 в позиции j > i. Теперь предположим, что мы поменяем эти два элемента. Элемент 1 был подтолкнут j-i позиции вправо, поэтому его вклад в шкалу будет уменьшаться на j-i. Но элемент 2 был сдвинут j-i позиции влево, поэтому его вклад в счет будет увеличен на j-i. Они сокращаются, оставляя общий балл неизменным.

Теперь любая перестановка элементов может быть достигнута путем замены элементов следующим образом: замените элемент в позиции 1 на элемент, который должен находиться в позиции 1, затем сделать то же самое для позиции 2 и т.д. После i-го шага правильны первые i-ые элементы перестановки. Мы знаем, что каждый своп оставляет неизменную функцию подсчета, а перестановка - это всего лишь последовательность свопов, поэтому каждая перестановка также оставляет неизменную функцию подсчета очков! Это верно для d элементов на обоих концах выходного массива.

Когда существуют 3 или более копий числа, только позиция первой и последней копии влияет на расстояние для этого числа. Не важно, куда идут средние. Я буду называть элементы между двумя блоками из d элементов с обоих концов "центральными" элементами. Они состоят из уникальных элементов, а также некоторых копий всех тех неповторимых элементов, которые появляются не менее 3 раз. Как и прежде, легко видеть, что любая перестановка этих "центральных" элементов соответствует последовательности свопов и что любой такой своп оставит неизмененный общий балл (на самом деле он еще проще, чем раньше, так как замена двух центральных элементов не даже изменить вклад оценки одного из этих элементов).

Это приводит к простому алгоритму O (nlog n) (или O (n), если вы используете сортировку ведра для первого шага) для создания массива решений Y из входного массива длины n:

• Сортировка входного массива X.
• Используйте один проход через X, чтобы подсчитать количество отдельных неповторимых элементов. Назовите это d.
• Установите i, j и k в 0.
• Хотя я < п:
  • Если X [i + 1] == X [i], мы имеем неповторимый элемент:
    • Установить Y [j] = Y [n-j-1] = X [i].
    • Приращение я в два раза и инкремент j один раз.
    • Хотя X [i] == X [i-1]:
      • Установить Y [d + k] = X [i].
      • Приращение я и k.
  • В противном случае мы имеем уникальный элемент:
    • Установить Y [d + k] = X [i].
    • Приращение я и k.