在阵列中排列0和1

这是我最近的面试问题之一.我想知道其他人对这个问题的看法.

题:

您将获得一个结构,其中包含两个元素(int部门和string名称)的员工详细信息.

struct Employee
{ 
    string Name;
    int Dept;
}

您将获得N员工的详细信息,其中N/2名员工Dept == 0和N/2名员工Dept == 1,按任意顺序排列.您需要根据其Dept值来对员工详细信息进行排序,并且应该是稳定的,即应保持原始记录中的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),其他变量具有恒定的空间(这意味着应该就地进行排序).

1> Antti Huima..：

---

分配第二个数组(O(N)).迭代第一个数组并按照它们出现的顺序将所有1移动到第二个数组.再次迭代并将以相同顺序保留的0移动到第二个数组.所有操作O(N).这不是原位(就地)解决方案.通过运行Quicksort分区算法一次获得非稳定的原位解.

在进行一些研究之后,似乎没有任何额外记忆的已知O(N)解决方案不稳定.有关有效0-1稳定原位分选(就地)的学术研究,但解决方案需要一些额外的记忆.我想知道原始问题陈述是否没有以精确的方式再现.没有稳定性要求问题很容易; 没有现场要求也很容易.满足要求(原位,稳定),解决方案似乎难以捉摸.

在这里的答案中,有一种算法在O(N)中工作并且是原位的,但只有当关键字段是(1)可变的并且(2)可以包含整数而不是单个位时.这可以工作,但不是原位0-1稳定排序,因为假设每个数组元素有可用的O(log N)可写内存.

2> Ganesh M..：

---

哦,这是我的方法.

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

伪代码:

有两个柜台,count1 = 0和count2 = (n/2)+1

遍历阵列,

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

在遍历结束时,您的数组填充数字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

注意:j循环只运行两次,与'n'无关,并且具有恒定的复杂性.整个循环的顺序是2*n = O(n).

该阵列被排序之后,再次通过阵列遍历并设置元件arr[0]以arr[n/2]向'1'和arr[(n/2)+1]到arr[n]作为'0'.

空间复杂度是恒定的,时间复杂度是O(步骤2)+ O(步骤4)+ O(步骤5)= n + 2n + n = 4*n = O(n).

---

这种方法分配额外的内存而不是原位排序,因为实际的位可能存储在1位宽的位域中.

---

@Ganesh:antti.huima是正确的:虽然您没有使用原始结构数组的整个副本,但您仍然使用O(n)额外空间来保存arr [].

3> MartinStettn..：

---

使用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)中执行.