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

Just want to rearrange the data in array so that similar items are not next to each. The data should not be removed from the array, if it can't be rearranged it can be put at the end of the array. But keeping the original order is necessary.

只想重新排列数组中的数据,以便类似的项目不在每个数据旁边。不应该从数组中删除数据,如果无法重新排列,则可以将数据放在数组的末尾。但保持原始秩序是必要的。

Example

   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: Added example to show keeping original order is needed

编辑:添加示例以显示需要保持原始顺序

8 个解决方案

#1

1. Sort your array

对数组进行排序

2. Swap elements at small even indexes with their higher antipodal counterparts:

   在较小的偶数指数上交换元素,使其具有更高的对映对应物:

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

Edit: Okay, we should redefine the antipodal counterparts. Maybe this one is better: mixing the first and third quartile (denoted x, y in illustration), and mixing the second and third quartile (denoted u, v, w). Let the counterparts ascend parallel.

编辑:好的,我们应该重新定义对映对手。也许这个更好:混合第一和第三四分位数(在图中表示为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

#2

Hmm. Bubblesort comes to mind, but with a three-element comparison; that is, if item[x] and item[x + 1] are the same and item[x + 2] is different, swap item[x + 1] and item[x + 2]. Repeat iterating through the list until no swaps occur. Execution order is, of course, horrible, but that should meet your needs.

嗯。想到Bubblesort,但有三元素比较;也就是说,如果item [x]和item [x + 1]相同且item [x + 2]不同,则交换项[x + 1]和item [x + 2]。重复遍历列表,直到没有发生交换。执行顺序当然是可怕的,但这应该满足您的需求。

#3

After I grasped what you're after, here's a possible solution

在我掌握了你所追求的东西之后,这是一个可能的解决方案

1. Partition your array

   对数组进行分区

   [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]]
   

   (read 3 times 1, 3 times 8, and so on)

   (阅读3次1,3次8次,依此类推)

2. For each partition entry i with p[i][0] >1 (times >1):

   对于每个分区条目i,其中p [i] [0]> 1(次> 1):

   • Choose a "valid" position j (so p[j][1] != p[i][1] && p[j+1][1] != p[i][1])

     选择“有效”位置j(所以p [j] [1]!= p [i] [1] && p [j + 1] [1]!= p [i] [1])

   • Decrement p[i][0] element and insert [p[i][1],1] in partition at position j

     递减p [i] [0]元素并在位置j的分区中插入[p [i] [1],1]

   or leave it out if there is no such position.

   如果没有这样的职位,请将其留下。

This should have linear time complexity (book-keep valid positions for each number).

这应该具有线性时间复杂度(每个数字的书籍保持有效位置)。

#4

Populate your array into a class var, then you can run your custom sort methods on it without changing it. Congratulations, you just created a new nosql database.

将数组填充到类var中,然后就可以在其上运行自定义排序方法而无需更改它。恭喜,您刚刚创建了一个新的nosql数据库。

What is scaring everyone is losing the original order.

什么吓到每个人都失去了原来的秩序。

This is why the key in a hash is called 'index', think about it.

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

}

#5

Java: Something like this?

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

#6

In javascript, I'd probably do:

在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++;
        }
    }

This is a quick example, coding style could probably be cleaned up a lot

这是一个快速的例子,编码风格可能会被清理很多

#7

Assuming A Array Containing Digits Between 0 To 9:
Similar To Bucket Sort In A Way

假设一个包含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--;
}

#8

Take the entire array and scan it for duplicates. When you encounter dupes, remember where they are. So for something like 2 1 2 2* 3 3* 3* 4 4* 2 2* 5. The ones with stars should be remembered.

获取整个阵列并扫描它以获得重复数据。遇到傻瓜时,请记住它们的位置。所以对于像2 1 2 2 * 3 3 * 3 * 4 4 * 2 2 * 5这样的东西应该记住那些有星星的东西。

Now look at the "Remembered" stuff, you have 2 2's, 2 3's and a 4

现在看看“记住”的东西,你有2 2,2 3和4

Now I'd sort those LISTS the most numerous first (2's and 3's) to the least numerous (4's)

现在我将那些LISTS排在最前面(2和3)最少数(4个)

Now just take the most numerous that doesn't duplicate the current "Front" (which would be 3 because 2 duplicates) and move it to the front, then remove it from your list.

现在只需要使用最多的不会复制当前“Front”(由于2个重复而为3)并将其移到前面,然后将其从列表中删除。

repeat until the lists are empty. The second time through your list will start with "3" and you will have 2 2's a 3 and a 4, so you'll put one of the 2's in the front...

重复直到列表为空。第二次通过你的列表将从“3”开始,你将有2 2的3和4,所以你将把2中的一个放在前面......

If you have any left (it can only be one number) put it at the end..

如果你有任何左边(它只能是一个数字)把它放在最后..

done, cake.