如何重新排列数组中的数据，以便两个相似的项目彼此不相邻？

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]或离开它，如果不存在这样的位置。

这应该有线性时间复杂度（书保持每个数字的有效位置）。