将0和1排列成一个数组

一尘不染

将0和1排列成一个数组

algorithm

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

题：

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

struct Employee
{ 
    string Name;
    int Dept;
}

将为您提供N名雇员的详细信息，其中N / 2名雇员Dept == 0和N / 2名雇员Dept == 1以任意顺序排列。您需要根据员工的Dept值对员工详细信息进行排序，并且应保持稳定，即应保持原始记录中1s和0s的顺序。

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

名字部

X1 0
X2 1
X3 0
X4 1
X5 0

排序后的结果应该是：

名字部

X2 1
X4 1
X1 0
X3 0
X5 0

该算法应稳定并且时间复杂度应为O（N），并为其他变量提供恒定的空间（这意味着应就地进行排序）。

阅读 175

2020-07-28

共1个答案

一尘不染

Okey，这是我的方法。

例如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<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]为as '0'。

空间复杂度是恒定的，时间复杂度是O（step2）+ O（step4）+ O（step5）= n + 2n + n = 4 * n = O（n）。

2020-07-28