如何重新排列數組中的數據，以便兩個相似的項目彼此不相鄰？

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 

編輯： 新增爲例，說明保持原有的以在需要

Answer 1

的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; 
     } 
     } 
    } 
    } 
} 

Answer 2

嗯。 Bubblesort浮現在腦海中，但有三個元素的比較;也就是說，如果item[x]和item[x + 1]是相同的，並且item[x + 2]是不同的，則交換item[x + 1]和item[x + 2]。重複遍歷列表，直到不出現交換。執行順序當然是可怕的，但那應該符合你的需求。

Answer 3

將您的數組填充到類var中，然後您可以在其上運行自定義排序方法而不更改它。恭喜，您剛剛創建了一個新的nosql數據庫。

嚇到大家的是什麼都失去了原來的秩序。

這就是爲什麼散列中的關鍵字被稱爲'索引'，想一想。

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 4

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 5

在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 6

假設數組包含數字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 7

取整個陣列並掃描重複項。當你遇到困惑時，記住他們在哪裏。所以對於像2 1 2 2 * 3 3 * 3 * 4 4 * 2 2 * 5這樣的東西應該記住。

現在看 「記憶」 的東西，你有2個2的，2 3的和4

現在我無數那些列出了最無數個第一（2的和3的）到最低排序（4'S）

現在只是採取最多的不重複當前的「前」（這將是3，因爲2重複），並將其移動到前面，然後將其從您的列表中刪除。

重複，直到列表爲空。第二次通過你的名單將從「3」開始，你將有2 2的一個3和一個4，所以你會把其中一個2在前面...

如果您有任何遺留（它只能是一個號碼）把它放在最後..

做完了，蛋糕。

Answer 8

後，我抓住你以後，這裏有一個可能的解決方案

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]元件和在位置j

   在分區插入[p[i][1],1]或離開它，如果不存在這樣的位置。

這應該有線性時間複雜度（書保持每個數字的有效位置）。