在数组中排列0和1

Question

这是我最近面试遇到的一个问题。我想知道别人对解决这个问题的看法。

问题：

给你一个结构体，其中包含两个元素，一个是整型部门，另一个是字符串姓名，用于保存员工详细信息。

struct Employee
{ 
    string Name;
    int Dept;
}

您将得到N个员工的详细信息，其中N/2个员工具有Dept == 0，另外N/2个员工具有Dept == 1，以任意顺序排列。您需要根据其Dept值对员工详细信息进行排序，且应该stable，即原始记录中1和0的顺序应该保持不变。

例如，给定以下示例数据：

Name         Dept
X1           0
X2           1
X3           0
X4           1
X5           0

排序后结果应该是：

Name         Dept
X2           1
X4           1
X1           0
X3           0
X5           0

算法应该是稳定的，并且时间复杂度应该为O(N)，对于其他变量来说空间应该是常数级别的（这意味着应该在原地进行排序）。

- Ganesh M

---

你是指小o(O(N))还是大O(O(N))？ - Johannes Weiss

@Johannes：+1 :) 但它真的不能是O（N）。 - Anton Tykhyy

我们可以假设，但这不是问题的关键。记住这是一道面试题，你要么给出一个答案并加以辩护，要么提出问题以澄清。 - sharptooth

问题和“简化版本”不同意1值应该在左侧还是右侧。编辑他人问题的人应该更加小心。 - dwc

你可能也想修改问题标题！ - Garry Shutler

Answer 1

分配第二个数组 (O(N))。遍历第一个数组，并按它们出现的顺序将所有的 1 移到第二个数组中。再次遍历并以相同顺序将剩下的 0 移到第二个数组中。所有操作 O(N)。这不是原地解决方案。通过运行 Quicksort 分区算法一次可以得到非稳定的原地解决方案。

经过一些研究，似乎已知的没有额外内存的 O(N) 解决方案都不稳定。有关在原地进行高效的 0-1 稳定排序的学术研究，但这些解决方案需要一些额外的内存。我想知道原问题陈述是否没有精确地复制。如果没有稳定性要求，则问题非常简单；如果没有原地要求，则问题也很容易解决。对于两个要求（原地，稳定）同时存在的情况，解决方案似乎难以找到。

在这里的答案中，有一种算法可以在 O(N) 的时间复杂度内解决问题，并且是原地的，但前提条件是键字段是可变的并且可以包含整数而不是单个位。这种方法有效，但不是原地的 0-1 稳定排序，因为假设每个数组元素可用 O(log N) 的可写内存。

- antti.huima

---

如果您有创建新数据结构的余地，则这是一个不错的选择。有时要求是“原地”，但没有提到，因此这是我认为最好的选择。 - Adam Davis

由于问题定义了数据中零和一的确切数量（N/2），因此您应该能够在一次遍历中完成传输。 - e.James

eJames：已知计数如何帮助？您总是可以在额外的O（N）遍历中计算元素数量吗？ - Antti Huima

当计数已知为N/2时，您知道第一个0应该放在插槽N/2中，第二个0应该放在插槽N/2+1中，以此类推。因此，您可以在第一次遍历中处理0。 - Michael Borgwardt

@Michael 你说的是对的，但它并没有以任何明显的方式导致原地排序算法。假设你找到了第一个1，并且你知道它属于N/2单元格；现在你想将这个1定位在N/2单元格中，并且你需要交换当前单元格中的对象——但是要知道那个对象需要去哪里，你需要计算0和N/2之间所有对象的数量！ - Antti Huima

它并没有解决内存问题，但它确实产生了更高效的算法。 - sh1

Answer 2

好的，这是我的方法。

例如：a[] = { 1,0,0,0,1,1,1,0,0,1};

伪代码:

1. 有两个计数器，count1=0和count2=(n/2)+1

2. 遍历数组，

   if(arr[ i ] == 1) 
   { 
       arr[ i ] = count1++;
   } else { 
       arr[ i ] = count2++ 
   };
   

3. 遍历结束后，你将得到一个填满了从0到n-1的数字的数组，例如：

a[ ] = { 0, 5, 6, 7, 1, 2, 3, 8, 9 4}

现在问题在于对上述结果数组进行排序，可以使用以下方法以 O(N) 的时间复杂度完成：

for(j = 0; j <= 1; j++)  
{
    for(i = 0; i<n; i++)  
    {  
        if(arr[ i ] != i)  
        {  
            swap(arr[ i ], arr[ arr[ i ] ]);  
        }  
    }  
}

注意：j循环无论'n'是多少，都只运行两次，并且具有固定的复杂度。整个循环的顺序为2*n = O(n)。

在数组排序后，再次遍历数组并将元素 arr[0]到arr[n/2]设置为'1'，将arr[(n/2)+1]到arr[n]设置为'0'。

空间复杂度为常数，时间复杂度为O(step2) + O(step4) + O(step5) = n + 2n + n = 4*n = O(n)。

- Ganesh M

---

这很聪明，Ganesh。我找不到任何漏洞。 - James McMahon

这种方法分配了额外的内存，不是原地排序，因为实际位可能存储在1位宽的位域中。 - Antti Huima

@nemo 是的，如果这样假设，但最初问题是以对比位排序的形式提出的，而作者因为有（无用的）关于“位不可区分”的评论而改写了它。0-1排序是一个明确定义的研究主题，而常数空间意味着没有额外的O(N)空间。 - Antti Huima

@Ganesh：antti.huima是正确的：尽管您没有使用原始结构数组的整个副本，但仍然需要使用O(n)的额外空间来保存arr[]。 - j_random_hacker

我知道我有点晚了，但这个算法是不正确的。请参见http://codepad.org/gmPkO3lz以获取反例和正确版本。 - tom

Answer 3

使用std::stable_partition和std::equal_to以及std::binder1st一起，可以用一种漂亮、功能强大、类似STL的方式完成任务：

using namespace std
stable_partition(&array[0], &array[N], binder1st(equal_to(), 1));

当然，这假设数组元素有一些比较操作符定义（即你可以说array[i]==1...）。如果它们只是整数，则维护顺序没有任何意义...

关于复杂度：为了达到O(N)，stable_partition需要额外的内存。如果算法无法分配该额外内存，则其性能为O(N log N)。

- MartinStettner

Answer 4

为简单起见，使用int而不是bit，但基本概念相同。请注意，不同的1和0的顺序很重要！

var emps = new[] 
           {
               new Employee(X1, 0),
               new Employee(X2, 1),
               new Employee(X3, 0),
               new Employee(X4, 1),
               new Employee(X5, 0),
               new Employee(X6, 1)
           };

var sortedEmps = new Employee[bits.Length];

var oneIndex = 0;
var zeroIndex = bits.Length/2;

foreach (var employee in employees)
{
    if (employee.Dept  == 1)
        sortedEmps[oneIndex++] = employee;
    else
        sortedEmps[zeroIndex++] = employee;
}

更新了针对员工问题的处理。由于原问题中说有N/2个员工，因此需要添加一个额外的员工，以确保员工数量为偶数才能满足条件。其他部分没有变化。

不确定现在是否可以编译，所以将其视为伪代码！

- Garry Shutler

---

双倍内存但单次遍历，我认为这将使其成为O(n)，如果我的O符号知识不错的话。 - Garry Shutler

Answer 5

原始问题描述中没有提到除整数外的其他字段（此后已被编辑）。

在这种情况下，稳定性没有意义，因为两个相等的数字是无法区分的。解决方案是遍历数组，将1放置n/2次，然后将0放置n/2次。

- sharptooth

---

不，它不是...只需想象输入是一个包含名称和整数值的结构体。然后顺序应该保持不变。 - Ganesh M

问题中没有“结构”。 - sharptooth

只有在键相等的情况下，稳定性才有意义。 - Bill the Lizard

@Bill：是的，但是当你只有键而没有卫星数据（值）时不行。这是对所提问的问题的完美回答。 - ShreevatsaR

@ShreevatsaR：没错，但我认为这并不能让你在面试中脱身。面试官可以自由地说：“假设有卫星数据，您将如何解决这个问题？” - Bill the Lizard

Answer 6

这将是基数排序的第一步。

- vartec

---

好的。这证明了你可以在O(n)的性能下完成它，但永远不可能是原地或具有常数空间复杂度。 - ashawley

Answer 7

这里有一个适用于 int 数组的解决方案。您可以进行修改。

sort (int [] a) {
   int pos = 0;
   for (int i = 1; i < a.length; i++) {
       if (a[i] == 0 && a[pos] == 1) {
           swap(a, pos, i);   // this makes all 0's go to the left.
           pos++;
       }
   } 
}

- fastcodejava

Answer 8

可以在单次遍历和原地完成。

1. 为索引变量取两个变量。一个将指向第0个位置，另一个将指向最后一个元素的位置。
2. 循环直到索引变量相等或交叉。
3. 从第一个位置搜索值1，从最后一个位置搜索值0，然后交换这两个元素。在一次遍历中，我们可以在O(n)时间内对数组进行排序。

例如： #include #define N 6 int main() { int list[N]={1,1,0,0,0,0}; int s,end,tmp; s=0;end=N-1;

    while(s less than end)
    {
        if(list[s]==1)
        {
            while(list[end] == 1) 
               end--;

            if(list[end] == 0 && s less than end)
            {
                tmp = list[s];
                list[s] = list[end];
                list[end] = tmp;
                s++;end--;
            }
        }
        else s++;
    }
    for(s=0;s less than N;s++)
    {
        printf("%d ",list[s]);
    }
    return;
}

- Esh

---

这个排序算法的时间复杂度为O(n)，空间复杂度为O(1)，但它不是稳定的。 - John Kurlak

Answer 9

#include<stdio.h>
//#include<conio.h>

int main()
{
  int i,a[20]={0};
  int *ptr1,*ptr2;
  //clrscr();
  //a[2]=a[4]=a[6]=a[8]=a[16]=1;
  a[19]=a[18]=1;

  for(i=0;i<20;i++)
    printf("%d",a[i]);

  printf("\n\nafter");

  ptr1=ptr2=a;
  for(i=0;i<20;i++)
  {
    if(*ptr1==0&&*ptr2==1)
    {
      int temp=*ptr1;*ptr1=*ptr2;*ptr2=temp;
      ptr1++;ptr2++;
    }
    else if(*ptr1==1&&*ptr2==0)
    {
      ptr1++;ptr2++;
    }
    else if(*ptr1==0&&*ptr2==0)
    {
      ptr2++;
    }
    else
    {
      if(ptr1<ptr2)
        ptr1++;
      else
      {
        ptr1++;ptr2++;
      }
    }
  }

  for(i=0;i<20;i++)
  {
    printf("%d",a[i]);
  }

 // getch();

  return 0;
}

- vijaikumar.m

Answer 10

这是整个解决方案： arr是项目列表，item.id为0或1，存储为int。
此代码将0移动到前面。

count = { 0:0, 1:len(arr)/2 }
for ii in range(len( arr )):
  id = arr[ii].id
  arr[ii].id = count[id]
  count[id] += 1
for ii in range(len( arr )):
  while arr[ii].id != ii:
    T = arr[ii]
    arr[ii] = arr[arr[ii].id]
    arr[T.id] = T
for ii in range(len( arr )):
  arr[ii].id = (ii >= len(arr)/2)

- Sanjaya R

---

我认为这是O(N)的正确排序，但不是原地排序，因为计数器可能需要比实际位数更多的内存。 - Antti Huima

根据问题描述，字段“Dept”是一个整数，因此假设arr[ii].id是arr[ii].Dept。完成了，没有额外开销。 - Sanjaya R

是的...根据当前的问题描述。但最初的问题是将一系列位排序... - Antti Huima