面试测试 - 重新排列数组 [英] Interview test - rearrange the array

问题描述

可能的重复:
数组元素的重新排序

在给定的元素数组中，如 [a1,a2,a3,..an,b1,b2,b3,..bn,c1,c2,c3,...cn] 编写一个程序来合并它们，如 [a1,b1,c1,a2,b2,c2,...an,bn,cn].我们必须在 O(1) 额外空间中完成.

In given array of elements like [a1,a2,a3,..an,b1,b2,b3,..bn,c1,c2,c3,...cn] Write a program to merge them like [a1,b1,c1,a2,b2,c2,...an,bn,cn]. We have to do it in O(1) extra space.

示例测试用例:

Input #00:

{1,2,3,4,5,6,7,8,9,10,11,12}

Output #00:

{1,5,9,2,6,10,3,7,11,4,8,12}

Explanation:

Here as you can notice, the array is of the form
{a1,a2,a3,a4,b1,b2,b3,b4,c1,c2,c3,c4} 

我在亚马逊安置测试中得到了它.已经尝试了很长时间了.请提供伪代码.我尝试的是为第二个元素 e(第一个已经在正确位置)找到新的位置 p，在 p 处插入 e 并在位置 p 的旧元素上重复相同的操作.但这是在一个循环中结束.我尝试检测循环并将起始位置增加 1.但即使这样也不起作用.

I got it in Amazon placement test. Have been trying it for a long time. PLease provide psuedo code. What i tried is finding new position p for second element e(1st is already at correct position), inserting e at p and repeating the same for the old element at position p. But this is ending in a cycle. I tried detecting cycle and incrementing the starting position by 1. But even this is not working.

#include <iostream>
using namespace std;

int pos(int i, int n) 
{
    if(i<n)  
     {
         return  3*i;

           }

       else if(i>=n && i<2*n)
       {

            return 3*(i-n) + 1;
            }
    else if(i>=2*n && i<3*n)
       {
            return 3*(i-2*n) + 2;
            }
return -1;
}
void printn(int* A, int n)
{
         for(int i=0;i<3*n;i++)  
             cout << A[i]<<";";

    cout << endl;
     }

void merge(int A[], int n)
{
 int j=1;    
 int k =-1;
 int oldAj = A[1];
 int count = 0;
 int temp;
 while(count<3*n-1){

 printn(A,n);
 k = pos(j,n);
 temp = A[k];
 A[k] = oldAj;
 oldAj = temp;
 j = k;
 count++;
 if(j==1) {j++;}
}

 }

int main()
{
    int A[21] = {1,4,7,10,13,16,19,2,5,8,11,14,17,20,3,6,9,12,15,18,21};
    merge(A,7);

    cin.get();}

推荐答案

这就是所谓的 in-place in-shuffle 算法，如果你想高效地完成它，这是一项极其艰巨的任务.我只是发布这个条目，所以人们不会发布他们所谓的解决方案"，声称它可以扩展到使用 O(1) 空间，而无需任何证明......

This is the so called in-place in-shuffle algorithm, and it's an extremely hard task if you want to do it efficiently. I'm just posting this entry so people don't post their so called "solutions" claiming that it can be extended to work with O(1) space, without any proof...

当列表为以下形式时，这里有一篇关于更简单情况的论文:a1 a2 a3 ... an b1 b2 b3 .. bn:

Here is a paper for a simpler case when the list is in the form: a1 a2 a3 ... an b1 b2 b3 .. bn:

http://arxiv.org/PS_cache/arxiv/pdf/0805/0805.1598v1.pdf

这篇关于面试测试 - 重新排列数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！