排列0和放大器; 1在一个阵列 [英] Arrange 0's & 1's in a array

问题描述

这是一个面试问题，我最近有一个。我想知道的方法别人感觉这个问题。

This is one of an interview question which I had recently. I would like to know others perception of approach for this problem.

问：

您将得到一个结构，其中包含员工详细信息有两个元素， INT 部门和字符串的名字。

You are given a structure which holds employee details with two elements, int department and string name.

struct Employee
{ 
    string Name;
    int Dept;
}

正在指定N员工的详细信息，其中N / 2的员工有部== 0 和N / 2的员工有部== 1 ，安排在一些任意顺序。你需要根据自己的部门价值的员工详细信息进行排序，它应该是的稳定即应保持1和0的原记录的顺序。

You are given details of N Employees, among which N/2 employees have Dept == 0 and N/2 employees have Dept == 1, arranged in some arbitrary order. You need to sort the employee details based on their Dept value and it should be stable i.e., the order of 1s and 0s in the original record should be maintained.

例如，考虑下面的示例数据：

For example, given the following sample data:

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），对其他变量恒定的空间（这意味着排序应就地进行）。

The algorithm should be stable and the time complexity should be O(N), with constant space for additional variables (which means sorting should be done in-place).

推荐答案

欧凯，这里是我的方法。

Okey, here is my approach.

例如一个[] = {1,0,0,0,1,1,1,0,0,1};

e.g a[] = { 1,0,0,0,1,1,1,0,0,1};

伪code：

1. 有两个计数器， COUNT1 = 0 和 COUNT2 =（N / 2）+1

2. 通过数组导线，

1. Have two counters, count1 = 0 and count2 = (n/2)+1

2. Traverse through the array,

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

在遍历结束时，你已经阵列写满数字0到n-1这样的：

At the end of the traversal, you have array filled with numbers 0 to n-1 like:

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

现在问题就来了上述合成数组排序，这可以在O（N），如下进行：

Now the problem comes to sort the above resultant array, this can be done in O(N) as below:

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）。

Note: j loop runs only twice irrespective on 'n' and has constant complexity. The order of this whole loop is 2*n = O(n).

在数组排序，通过数组再次穿越，并设置元素改编[0] 到改编[N / 2] 到 1 和改编[（N / 2）+1] 到改编[N] 为 0 。

After the array is sorted, Again traverse through the array and set elements arr[0] to arr[n/2] to '1' and arr[(n/2)+1] to arr[n] as '0'.

空间复杂度是恒定的时间复杂度为O（步骤2）+ O（第四步）+ O（步骤5）= N + 2 N + N = 4 * N = O（N）。

Space complexity is constant and time complexity is O(step2) + O(step4) + O(step5) = n + 2n +n = 4*n = O(n).

这篇关于排列0和放大器; 1在一个阵列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！