Как переставить данные в массиве, чтобы два одинаковых элемента не были рядом друг с другом?

Question

Просто хочу переставить данные в массив так, чтобы похожие элементы не были рядом с каждым. Данные не должны быть удалены из массива, если их нельзя переставить, их можно поместить в конец массива. Но соблюдение первоначального порядка необходимо.

Пример

   1 1 2             =>   1 2 1 
   1 1 1 2 3         =>   1 2 1 3 1
   1 1 2 1 3 3 5 1   =>   1 2 1 3 1 3 5 1
   1 1 1 1 1 1 2     =>   1 2 1 1 1 1 1
   8 2 1 3 7 2 5     =>   rearrange not needed
   8 2 2 2 7 2 5 2   =>   8 2 7 2 5 2 2      // keep the original order

EDIT: Добавлен пример для отображения необходимости сохранения оригинального заказа

Answer 1

1. Сортируй свой массив

2. Поменяйте местами элементы при небольших четных индексах с их более высокими антиподальными аналогами:

   for ( i=0; i < arr.length/2; i+=2 )
       arr.swap(i,arr.length-1-i);
   

Редактировать: Хорошо, мы должны переопределить антиподальные аналоги. Возможно, этот вариант лучше: смешать первый и третий квартиль (обозначен на рисунке x, y) и смешать второй и третий квартиль (обозначен как u, v, w). Пусть параллели поднимутся параллельно.

        25%  50%  75%
         |    |    |
    -----[----[----[----
    11122334455667788999
     x y u v w x y u v w  <-- u, v, w, x, y indicate swap positions
    16172839495161738495

Answer 2

Хм.На ум приходит Bubblesort, но с трехэлементным сравнением;то есть, если item[x] и item[x + 1] одинаковы, а item[x + 2] отличается, поменяйте местами item[x + 1] и item[x + 2].Повторяйте итерацию по списку, пока не произойдет перестановок.Порядок исполнения, конечно, ужасен, но он должен отвечать вашим потребностям.

Answer 3

После того, как я понял, что вы ищете, вот возможное решение

1. Разделите ваш массив

   [1,1,1,8,8,8,2,3,3,4,1,1,1,2,2] -> [[3,1],[3,8],[1,2],[2,3],[1,4],[3,1],[2,2]]
   

   (прочитайте 3 раза 1, 3 раза 8,и т. д.)

2. Для каждой записи раздела i с p[i][0] >1 (раз> 1):

   • Выберите «действительный»позиция j (т. е. p[j][1] != p[i][1] && p[j+1][1] != p[i][1])

   • Уменьшить p[i][0] элемент и вставить [p[i][1],1] в раздел в позиции j

   илиоставьте это, если такой позиции нет.

Это должно иметь линейную сложность по времени (вести учет правильных позиций для каждого числа).

Answer 4

Взять весь массив и отсканировать его на наличие дубликатов.Когда вы сталкиваетесь с обманщиками, помните, где они находятся.Так что для чего-то вроде 2 1 2 2 * 3 3 * 3 * 4 4 * 2 2 * 5. Нужно помнить те, у которых есть звезды.

Теперь посмотрим на материал "Помнят", у вас есть 2 2,2 3 и 4

Теперь я бы отсортировал эти СПИСКИ от первых самых больших (2 и 3) до наименее многочисленных (4)

Теперь просто возьмите самые многочисленные, которые непродублируйте текущий «Фронт» (который будет равен 3, потому что 2 дубликата) и переместите его на передний план, затем удалите его из списка.

повторяйте, пока списки не станут пустыми.Второй раз в вашем списке начнется с «3», и у вас будет 2, 2, 3 и 4, так что вы положите одну из 2 вперед ...

Если у вас осталось(это может быть только одно число) поставить его в конце ..

готово, торт.

Answer 5

Предполагается, что массив содержит цифры от 0 до 9:
По типу сортировки ведра по пути

int B[10];//buckets
diff=0;//how many different digits appeared

for(i=0;i<A.length;i++)
{
 x=A[i];
 if(B[x]==0)
 {
  diff++;
 }
 B[x]++;
}//loaded
while(diff>=0)//now to place back to array makes an interleaving
{
 for(digit=0;digit<10;digit++)
 {
  if(B[digit]<>0)
  {
   A[B[digit]+diff]=digit;
   B[digit]--;
  }
 }
 diff--;
}

Answer 6

В javascript я бы, наверное, сделал:

    var arr = [ 1, 1, 1, 2, 3 ];
    var i = 0, len = arr.length;

    while (i < len - 1) {
        if (arr[i] == arr[i+1]) {
            //index is equal to it's partner.
            if (arr[i+2] && arr[i] == arr[i+2]) {
                // 3 equal values in a row, swapping won't help. Need to recheck this index in this case.
                var tmp = arr[i];
                arr.splice( i, 1 );
                arr.push( tmp );
            } else {
                // Swap the next and 2nd next index.
                var tmp = arr[i+1];
                arr[i+1] = arr[i+2];
                arr[i+2] = tmp;
                i++;
            }
        } else {
            // this index is fine, move on.
            i++;
        }
    }

Это быстрый пример, стиль кодирования, вероятно, может быть сильно очищен

Answer 7

Заполните ваш массив в классе var, и вы сможете запускать на нем свои собственные методы сортировки, не изменяя его.Поздравляем, вы только что создали новую базу данных nosql.

То, что пугает всех, теряет первоначальный заказ.

Вот почему ключ в хэше называется index, подумайте об этом.

class Dingleberry
  {

   private $shiz= array();

    function __construct(array $a) { $this->shiz = $a; }

##### PUBLIC

    public function unmolested() { return $this->shiz; }

    /* @see http://www.php.net/manual/en/ref.array.php */
    public function sort($type)
        {
        switch ($type)
            {
            case 'key_reverse': return krsort($this->shiz); break;
            # Check all the php built in array sorting methods to 
                    # make sure there is not already one you want
                    # then build this out with your own
            }
        }

}

Answer 8

Java: как-то так?

void resortArray(ArrayList<Integer> arr) {
  for(int i = 0; i < arr.size(); i++) //loop trough array
    if(arr.get(i) == arr.get(i + 1)) { //if the next value is the same as current one
      for(int j = i+2; j < arr.size(); j++) { //loop again trough array from start point i+2
        if(arr.get(i+1) != arr.get(j)) { //swap values when you got a value that is different
          int temp = arr.get(i+1);
          arr.set(i+1, arr.get(j));
          arr.set(j, temp);
          break;
        }  
      }
    }
  }
}