当前位置： 文江博客话题详情

面试测试——重新排列数组

发布于 2024-12-15 07:24:05 字数 1577 浏览 0 评论 0原文

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

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

示例测试用例：

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。但即使这样也不起作用。

编辑2：

#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();}
原文

Possible Duplicate:
Reordering of array elements

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.

Sample Testcases:

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}

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

EDIT2:

#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();}

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（5）

喵星人汪星人 2024-12-22 07:24:06

这就是所谓的 in-place in-shuffle 算法，如果你想高效地完成它，这是一个极其困难的任务。我只是发布这个条目，这样人们就不会发布他们所谓的“解决方案”，声称它可以扩展到 O(1) 空间，而没有任何证据......

这是一篇关于更简单情况的论文，当列表的格式为：a1 a2 a3 ... an b1 b2 b3 .. bn：

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

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

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

回复 原文
孤独难免 2024-12-22 07:24:06

以下是具有 3 个额外空间元素和 O(n^2) 复杂度的算法的描述：

sa、sb、sc 分别是：分别是 a、b 和 c 序列的下一个源索引。
d 是复制目标索引。

在每个迭代中：

  • 将 sa、sb 和 sc 处的元素复制到临时存储

  • 将数组元素向左移动以填充现在空缺的索引sa ，sb 和sc

  • 这在 d 处留下了三个空位置

  • 将三个元素从临时存储复制到空位置.

示例（点表示“空”位置）：

First iteration:
 copy to tmp: ., 2, 3, 4,  ., 6, 7, 8,   .,10,11,12
              1            5             9
 shift:       ., ., ., 2,  3, 4, 6, 7,   8,10,11,12
 copy to dst: 1, 5, 9, 2,  3, 4, 6, 7,   8,10,11,12

Second iteration:
copy to tmp: 1, 5, 9, .,   3, 4, ., 7,   8, .,11,12
                      2          6         10
shift:       1, 5, 9, .,   ., ., 3, 4,   7, 8,11,12
copy to dst: 1, 5, 9, 2,   6,10, 3, 4,   7, 8,11,12

Third iteration:
copy to tmp: 1, 5, 9, 2,   6,10, ., 4,   ., 8, .,12
                                 3       7    11 
shift:       1, 5, 9, 2,   6,10, ., .,   ., 4, 8,12
copy to dst: 1, 5, 9, 2,   6,10, 3,  7  11, 4, 8,12

编辑：

这是一个工作程序（它需要的不仅仅是口头描述:)））

#include <stdio.h>

#define N 4

int a[] = {1, 2,3, 4, 5, 6, 7, 8, 9, 10, 11, 12};

void
rearrange ()
{
  int i;
  int d;
  int sa, sb, sc;
  int tmp [3];

  d = 0;
  sa = 0;
  sb = sa + N;
  sc = sb + N;

  while (sc < N*3)
    {
      /* Copy out.  */
      tmp [0] = a [sa];
      tmp [1] = a [sb];
      tmp [2] = a [sc];

      /* Shift  */
      for (i = sc; i > sb + 1; --i)
        a [i] = a [i - 1];

      for (i = sb + 1; i > sa + 2; --i)
        a [i] = a [i - 2];

      sa += 3;
      sb += 2;
      sc++;

      /* Copy in.  */
      a [d++] = tmp [0];
      a [d++] = tmp [1];
      a [d++] = tmp [2];
    }
}

int
main ()
{
  int i;
  rearrange ();

  for (i = 0; i < N*3; ++i)
    printf ("%d\n", a [i]);
  putchar ('\n');
  return 0;
}

似乎可以工作。 耸耸肩

Here's is a description of an algorithm with 3 elements of extra space and O(n^2) complexity:

sa, sb, sc are, respectively, next source index for a, b and c sequences.
d is the copy destination index.

On each iterarion:

  • Copy elements at sa, sb and sc to temporary storage

  • Shift the array elements to the left to fill in the now vacant indices sa, sb and sc

  • This leaves three empty positions at d

  • Copy the three elements from temporary storage to empty positions.

Example (dots indicate "empty" positions):

First iteration:
 copy to tmp: ., 2, 3, 4,  ., 6, 7, 8,   .,10,11,12
              1            5             9
 shift:       ., ., ., 2,  3, 4, 6, 7,   8,10,11,12
 copy to dst: 1, 5, 9, 2,  3, 4, 6, 7,   8,10,11,12

Second iteration:
copy to tmp: 1, 5, 9, .,   3, 4, ., 7,   8, .,11,12
                      2          6         10
shift:       1, 5, 9, .,   ., ., 3, 4,   7, 8,11,12
copy to dst: 1, 5, 9, 2,   6,10, 3, 4,   7, 8,11,12

Third iteration:
copy to tmp: 1, 5, 9, 2,   6,10, ., 4,   ., 8, .,12
                                 3       7    11 
shift:       1, 5, 9, 2,   6,10, ., .,   ., 4, 8,12
copy to dst: 1, 5, 9, 2,   6,10, 3,  7  11, 4, 8,12

EDIT:

And here's a working program (it takes a bit more than a verbal description :)))

#include <stdio.h>

#define N 4

int a[] = {1, 2,3, 4, 5, 6, 7, 8, 9, 10, 11, 12};

void
rearrange ()
{
  int i;
  int d;
  int sa, sb, sc;
  int tmp [3];

  d = 0;
  sa = 0;
  sb = sa + N;
  sc = sb + N;

  while (sc < N*3)
    {
      /* Copy out.  */
      tmp [0] = a [sa];
      tmp [1] = a [sb];
      tmp [2] = a [sc];

      /* Shift  */
      for (i = sc; i > sb + 1; --i)
        a [i] = a [i - 1];

      for (i = sb + 1; i > sa + 2; --i)
        a [i] = a [i - 2];

      sa += 3;
      sb += 2;
      sc++;

      /* Copy in.  */
      a [d++] = tmp [0];
      a [d++] = tmp [1];
      a [d++] = tmp [2];
    }
}

int
main ()
{
  int i;
  rearrange ();

  for (i = 0; i < N*3; ++i)
    printf ("%d\n", a [i]);
  putchar ('\n');
  return 0;
}

Appears to work. shrug

回复 原文
橘虞初梦 2024-12-22 07:24:06

这是像您这样的问题的一般解决方案。

首先，对于每个源索引，您都知道目标索引。现在，你就这样：

  1. 拿第一项。找到它的最终位置。记住该位置的项目，并将第一个项目存储在那里。现在，找到所记忆的项目所属的位置，并将该项目放在那里，记住被替换的项目。继续这个过程，直到到达第一个项目的位置（显然）。
  2. 如果您已更换了所有物品，则您已完成。如果没有，则取出第一个未转移的项目，并从该项目开始，继续从步骤 1 开始重复该过程。

您需要标记已转移的项目。有不同的方法可以做到这一点：例如，您可以使用项目存储中的一位。

好的，上面的解决方案并不完全是 O(1)，因为它需要 N 个额外位。以下是按位置进行 O(1) 解决方案的概述，尽管效率较低：

考虑项目 a1、b1、c1。它们需要位于结果的前 3 个位置。因此，我们正在执行以下操作：记住 a1、b1、c1，将除这三项之外的数组压缩到后面（因此看起来像这样： , , , a2, a3, ..., an, b2, b3, .. ., bn, c2, c3, ..., cn)，并将项目 a1, b1, c1 放在开头的位置。现在，我们找到了前 3 项的位置，因此对 a2、b2、c2 等继续此过程。

编辑：
让我们考虑一下上面概述的时间复杂度。表示列表大小3*n。我们需要n步。列表的每一次压缩都可以一次完成，因此时间复杂度为O(n)。步骤内的所有其他操作都是 O(1)，因此我们总共获得 n * O(n) = O(n^2) 复杂度。然而，这远不是最好的解决方案，正如 @yi_H 提到的，线性时间解决方案需要大量使用或多或少的高级数学。

This is the general solution to the problems like yours.

First of all, for each source index you know the destination index. Now, you go like that:

  1. Take the first item. Find its final place. Memorize the item at that place, and store the first item there. Now, find the place where the memorized item belongs to, and put that item there, memorizing that replaced item. Continue the process until it hits the place of the first item (obviously).
  2. If you've replaced all the items, you are finished. If not, take the first non-transferred item and continue repeat the procedure from step 1, starting with that item.

You'll need to mark which items you've transferred already. There are different ways to do it: for example, you can use one bit from the item's storage.

Okay, the solution above is not exactly O(1), as it requires N extra bits. Here is the outline of O(1) solution by place, though less efficient:

Consider the items a1, b1, c1. They need to be located at the first 3 places of the result. So we are doing the following: remembering a1, b1, c1, compacting the array except these three items to the back (so it looks like this: , , , a2, a3, ..., an, b2, b3, ..., bn, c2, c3, ..., cn), and put the items a1, b1, c1 at their places at the beginning. Now, we found the place for the first 3 items, so continue this procedure for a2, b2, c2 and so on.

Edit:
let's consider the time complexity of the outline above. Denote list size 3*n. We need n steps. Each single compactification of the list can be done in one pass, and therefore is O(n). All the other operations inside a step are O(1), so we get altogether n * O(n) = O(n^2) complexity. This is far from the best solution, however, as @yi_H mentions, linear-time solution requires heavy usage of more-or-less advanced mathematics.

回复 原文
痴骨ら 2024-12-22 07:24:06

我找不到任何 O(n) 算法，但这是 O(n^2) 就地算法，每次通过给定输入测试代码时，我都会将三元组移到最后，在 C# 中，可能有错误，如果是这样请告诉我：

        int[] a = new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 };
        int m = a.Length / 3;
        int firstB = a[m];

        for (int i = m-1; i > 0; i--)
        {
            int second = a[3 * m - 3];
            int third = a[3 * m - 2];
            //a[i + 2 * m] = a[i +2 * m];
            a[3 * m - 2] = a[2 * m - 1];
            a[3 * m - 3] = a[m - 1];
            for (int j = m - 1; j < 2 * m - 1; j++)
            {
                a[j] = a[j + 1];
            }
            for (int j = 2 * m - 2; j < 3 * m - 3; j++)
            {
                a[j] = a[j + 2];
            }
            a[3 * m - 5] = second;
            a[3 * m - 4] = third;
            m--;
        }
        a[1] = firstB;

I can't find any O(n) algorithm but this is O(n^2) in-place one, I'll move triples to the last each time code is tested by given input, is in C#, may be is buggy, If is so let me know:

        int[] a = new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 };
        int m = a.Length / 3;
        int firstB = a[m];

        for (int i = m-1; i > 0; i--)
        {
            int second = a[3 * m - 3];
            int third = a[3 * m - 2];
            //a[i + 2 * m] = a[i +2 * m];
            a[3 * m - 2] = a[2 * m - 1];
            a[3 * m - 3] = a[m - 1];
            for (int j = m - 1; j < 2 * m - 1; j++)
            {
                a[j] = a[j + 1];
            }
            for (int j = 2 * m - 2; j < 3 * m - 3; j++)
            {
                a[j] = a[j + 2];
            }
            a[3 * m - 5] = second;
            a[3 * m - 4] = third;
            m--;
        }
        a[1] = firstB;
回复 原文
寂寞笑我太脆弱 2024-12-22 07:24:06

这里我们有 x * y 数字：

a_11, a_12, ..., a_1x,
a_21, a_22, ..., a_2x,
...
a_y1, a_y2, ..., a_yx

那么数字 a_ij 在数组中具有索引 i*x + j；

程序结束后，新索引将

j * y + i

在您的面试中

{a1,a2,a3,a4,b1,b2,b3,b4,c1,c2,c3,c4}

x 为 4，y 为 3，

因此现在使用索引“n”，

i = (n - (n % 4)) / 4;
j = n % 4;

您可以使用 i, j, x, y 计算新索引代码>.

祝你好运。

Here we have x * y numbers:

a_11, a_12, ..., a_1x,
a_21, a_22, ..., a_2x,
...
a_y1, a_y2, ..., a_yx

then the number a_ij has the index i*x + j in an array;

after your program, the new index will be

j * y + i

in your interview

{a1,a2,a3,a4,b1,b2,b3,b4,c1,c2,c3,c4}

x is 4, and y is 3,

so with the index ``n''

i = (n - (n % 4)) / 4;
j = n % 4;

now you can calculate the new index with i, j, x, y.

Good Luck.

回复 原文
~没有更多了~

关于作者

挽清梦

暂无简介

0 文章
0 评论
596 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

小瓶盖

文章 0 评论 0

wxsp_Ukbq8xGR

文章 0 评论 0

1638627670

文章 0 评论 0

仅一夜美梦

文章 0 评论 0

夜访吸血鬼

文章 0 评论 0

近卫軍团

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文