admin管理员组

文章数量:1208153

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

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

• java
• javascript
• c++
• c
• algorithm

Share Improve this question Follow edited Nov 12, 2010 at 19:20 Mark K asked Nov 11, 2010 at 17:18 Mark KMark K 1,24433 gold badges2020 silver badges3131 bronze badges 10

• 4 You want to rearrange them, but keep the order....? – Nick Craver Commented Nov 11, 2010 at 17:19
• 2 @Mark - The two are mutually exclusive..either you keep the order or change it...can you clarify what you mean? – Nick Craver Commented Nov 11, 2010 at 17:21
• 2 instead of tagging any programming language you have thought of you could and should have tagged it with algorithm tag – Armen Tsirunyan Commented Nov 11, 2010 at 17:35
• This really sounds like a homework question--you might mention that in the question if it is--it will help people answer it correctly. – Bill K Commented Nov 11, 2010 at 17:40
• @Armen mentioned languages are not any programming language, they have similar syntax. That is why I mentioned them. – Mark K Commented Nov 11, 2010 at 19:22

 |  Show 5 more comments

7 Answers 7

Sorted by: Reset to default 10

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.

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

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.

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)

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

   • Choose a "valid" position j (so 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

   or leave it out if there is no such position.

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

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.

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

    
  

}

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

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

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.

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

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

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.

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

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

done, cake.

In javascript, I'd probably do:

    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

本文标签： javaHow to rearrange data in array so that two similar items are not next to each otherStack Overflow