代码之家 › 专栏 › 技术社区 › Zacky112

访谈问题:C程序在O(n)中对二进制数组进行排序

sorting algorithm arrays c

Zacky112 · 技术社区 · 15 年前

我已经想出了下面的程序来完成它,但它似乎不起作用,进入了无限循环。它的工作原理类似于快速排序。

int main()
{
 int arr[] = {1,1,0,1,0,0,0,1,0,1,0,1,0,1,0,1,0,1};
 int N = 18;
 int *front, *last;

 front = arr;
 last = arr + N;
 while(front <= last)
 {
  while( (front < last) && (*front == 0) )
   front++;

  while( (front < last) && (*last == 1) )
   last--;

  if( front < last)
  {
   int temp = *front;
   *front = *last;
   *last = temp;
   front ++;
   last--;
  }
 }
 for(int i=0;i<N;i++)
  printf("%d ",arr[i]);

 return 0;
}

16 回复 | 直到 8 年前

codaddict 15 年前

我在程序中看到了至少两个问题:

问题1:

last = arr + N;

是不正确的。应该是:

last = arr + N - 1;

因为

(arr + 0) points to 0th ele
(arr + 1) points to 1st ele
...
(arr + N -1) points to (N-1)th ele..which is the last element.

问题2:
下一个while循环:

while(front <= last)

不正确,应该是:

while(front < last)

在前面和最后一个相等的情况下,循环继续,但是无论前面还是最后一个都不会在这一点上被修改,导致无限循环。

当前面和最后一个相等时,就没有必要继续,你的数组那时就会被分类了。

pmg 14 年前

你是说这个数组只有 0 S和 1 S?

求和所有n个元素,然后覆盖数组:)

int main() {
    int arr[] = {1,1,0,1,0,0,0,1,0,1,0,1,0,1,0,1,0,1};
    int N = sizeof arr / sizeof *arr; /* 18 */
    int sum = 0;
    int ndx;
    for (ndx=0; ndx<N; ndx++) sum += arr[ndx];
    for (ndx=0; ndx<N-sum; ndx++) arr[ndx] = 0;
    for (ndx=N-sum; ndx<N; ndx++) arr[ndx] = 1;
}

sth 15 年前

您的算法的基本思想运行良好,可以简化实现:

int a[] = {1,1,0,1,0,0,0,1,0,1,0,1,0,1,0,1,0,1};

int *begin = a;
int *end = begin + 17;

while (begin < end) {
   if (*begin == 0)
      begin++;
   else if (*end == 1)
      end--;
   else {
      *begin = 0;
      *end = 1;
   }
}

注意 (begin < end) 是终止循环的一个更强有力的条件,并且在每次迭代中只执行一个操作(移动指针或交换值),简化代码并使其更容易理解循环将真正终止。

John Feminella 15 年前

你对自己太苛刻了!你只知道数组的大小就可以在o(n)中完成。 n 元素之和 S . 因为一个二进制数组对于每个元素只有两种可能,知道一个元素有多少个,并且总大小就足够了。

一旦知道了这一点,只需输出一个包含 S - n 零点和 n 按顺序排列。完成!

另一种不需要先求和并在适当位置工作的方法是:放置一个“写入”指针 w 在索引0和“读取”指针处 r 在索引N-1。使用读取指针向后迭代,每次遇到0时,在 W 并递增。当你开始 R ,用“1”填充数组的其余部分 W .

animuson 13 年前

void my_sort(int* arr, int n){
  int zero = -1;

  for(int i = 0; i < n;i++){
    if(arr[i] == 0){
      zero++; 
      swap(arr[zero],arr[i]);
    }
  }
}

保留最后一个零索引的轴,并从左到右交换所有数字,直到到达数组的末尾。

SF. 15 年前

如果您的目标是o(n)忽略所有quickport(nlogn)、bubblessets等。对于标准数据集,没有经典排序算法实现o(n),则必须利用集的二进制性质。

 int arr[] = {1,1,0,1,0,0,0,1,0,1,0,1,0,1,0,1,0,1};
 int N = 18;
 int i,s=0;
 for(i=0;i<N;i++) s+=(arr[i]==0);
 for(i=0;i<N;i++) arr[i]=!(i<s);

Chad Brewbaker 15 年前

过度杀戮,但您可以使用pang ko的线性时间后缀数组构造算法:

http://sites.google.com/site/kopangcn2/software2

那会让面试官大吃一惊的:P

Angel O'Sphere 14 年前

一般的解决方案(如果它不仅是0和1)被称为“按计数排序”。如果您知道数据在某个范围内,则始终可以使用它。例如,您希望按一组人的出生日期(不包括年份)对他们进行排序。您只需创建一个367(闰年)天的数组,该数组中的每个槽都是一个(链接的)列表,可以保存您的数据。现在,您将扫描您的数据,从Peerson的生日开始计算“一年中的某一天”,并将其添加到认可的列表中。

Tim Cooper 13 年前

int[] arr = { 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1 };

int left = 0;
int right = arr.Length-1;
int first = arr[left];
while (left < right)
{
    if (arr[left] == 0 && arr[right] ==1)
    {
        left++;
        right--;
    }
    else if (arr[left] == 1 && arr[right] == 1)
    {
        right--;
    }
    else if (arr[left] == 0 && arr[right] == 0)
    {
        left++;
    }
    else
    {
        arr[left] = 0;
        arr[right] = 1;
        left++;
        right--;
    }
}

Mecki 15 年前

您的代码不会在我的系统中进入无休止的循环:

# gcc $CFLAGS -o test test.c
# ./test
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

但是结果是错误的。我看到8乘以1,但应该是9乘以1。

正如一些人指出的,总结是一种简单得多的方法:

#include <stdio.h>

int main() 
{
    int i;
    int count;
    int N = 18;
    int arr[] = {1,1,0,1,0,0,0,1,0,1,0,1,0,1,0,1,0,1};

    /* Sum up all elements */
    i = 0;
    count = 0;
    while (i < N) count += arr[i++];

    /* Overwrite the array */
    i = 0;
    count = N - count;
    while (i < count) arr[i++] = 0;
    while (i < N) arr[i++] = 1;

    /* Print result */
    for (i = 0; i < N; i++) printf("%d ",arr[i]);
}

Escualo 15 年前

在这里转载,因为我回答的问题被关闭了(这个问题的副本)。

我很抱歉用python回答这个问题,但这是我想做的练习。这段代码的意思是冗长的,以输出算法的步骤。当然,转换为C并不困难,只要小心移动指针。干杯!

# Put zeros on the left, ones on the right in one pass                                                
a = [1,0,1,0,0,1,1,1,0,0,1,0,0,1,0,0,1,1,0,0,1,1,0,0,1,0,1]
cl = 0
cr = len(a) - 1
print a

while(True):
    if cl + 1 == cr:
        print 'last pass; adjacent elements'
        if a[cl] == 0:
            print 'a[%d] = 0; leave and exit loop' % (cl)
            print 'final array:'
            print a
            break
        if a[cl] == 1:
            print 'a[%d] = 1; try to swap with a[%d]' % (cl, cr)
            if a[cr] == 1:
                print 'a[%d] = 1 as well; leave and exit loop' % (cr)
                print 'final array:'
                print a
                break
            else:
                print 'a[%d] and a[%d] swapped; leave and exit loop' % (cl, cr)
                a[cl] = 0
                a[cr] = 1
                print 'final array:'
                print a
                break
    if a[cl] == 0:
        print 'a[%d] = 0; leave and move on to a[%d]' % (cl,cl+1)
        cl += 1
        continue
    else:
        print 'a[%d] = 1 move to the right' % (cl)
        while(True):
            if a[cr] == 1:
                print 'a[%d] cannot be moved to a[%d], try a[%d]' % (cl, cr, cr-1)
                cr -= 1
                continue
            else:
                print 'a[%d] swapped with a[%d]' % (cl, cr)
                a[cr] = 1
                a[cl] = 0
                cr -= 1
                cl += 1
                print 'next up: a[%d]; right side blocked up to %d' % (cl,cr)
                break
    if (cl + 1) == cr:
        break

样品输出:

[1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1]
a[0] = 1 move to the right
a[0] cannot be moved to a[26], try a[25]
a[0] swapped with a[25]
next up: a[1]; right side blocked up to 24
a[1] = 0; leave and move on to a[2]
a[2] = 1 move to the right
a[2] cannot be moved to a[24], try a[23]
a[2] swapped with a[23]
next up: a[3]; right side blocked up to 22
a[3] = 0; leave and move on to a[4]
a[4] = 0; leave and move on to a[5]
a[5] = 1 move to the right
a[5] swapped with a[22]
next up: a[6]; right side blocked up to 21
a[6] = 1 move to the right
a[6] cannot be moved to a[21], try a[20]
a[6] cannot be moved to a[20], try a[19]
a[6] swapped with a[19]
next up: a[7]; right side blocked up to 18
a[7] = 1 move to the right
a[7] swapped with a[18]
next up: a[8]; right side blocked up to 17
a[8] = 0; leave and move on to a[9]
a[9] = 0; leave and move on to a[10]
a[10] = 1 move to the right
a[10] cannot be moved to a[17], try a[16]
a[10] cannot be moved to a[16], try a[15]
a[10] swapped with a[15]
next up: a[11]; right side blocked up to 14
a[11] = 0; leave and move on to a[12]
a[12] = 0; leave and move on to a[13]
last pass; adjacent elements
a[13] = 1; try to swap with a[14]
a[13] and a[14] swapped; leave and exit loop
final array:
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

Community CDub 8 年前

显然另一个问题已经解决了…你的算法工作得很好。我发表的回应 maddy 表面上看 dup 在这里被一个关闭它的人重定向了

int main()
{
  int v[] = {1,1,0,1,0,0,0,1,0,1,0,1,0,1,0,1,0,1}; int *a, *b, i, n;
  n = sizeof(v) / sizeof(int);
  for (a = v, b = v + n - 1; a < b; ++a) {
    if (*a) {
      for (; *b; --b) if (a == b) goto end;
      *a = 0; *b-- = 1;
    }
  }
  end: for (i = 0; i < n; ++i) printf("%d%s", v[i], (i==n-1?"\n":",")); return 0;
}

将一些行移动到一起以使其适合页面….差不多一样

DarthJDG chetan borse 14 年前

以下是一个简单的答案:)

int main()
{
    int a[]={1,0,1,1,1,0,1,0,1},size=9,end_value,index1,index2=-1;
    end_value=a[size-1];
    for(index1=0;index1 < size-1;index1++)
    {
        if(a[index1]==end_value )
        {
            index2++;
            a[index2]=!a[index2];
            a[index1]=!a[index1];
        }
    }
    index2++;
    a[index2]=!a[index2];
    a[index1]=!a[index1];
}

Julio 12 年前

这可以用一个简单的二进制文件来完成。 counting sort :

#include <stdio.h>

int main()
{
    int N = 18, zeros=0, i;
    int arr[] = {1,1,0,1,0,0,0,1,0,1,0,1,0,1,0,1,0,1}, *ptr, *last;

    ptr = arr;
    last = arr + N - 1;
    while (ptr != last)
    {
        if (!*ptr) zeros++;
        ptr++;
    }

    for (i = 0; i < zeros; i++) arr[i] = 0;
    for (; i < N; i++) arr[i] = 1;

    for (i = 0; i < N; i++)
        printf("%d ", arr[i]);
    putchar('\n');

    return 0;
}

Ajo Thomas 12 年前

这应该很管用。只有一个循环可以完成这项工作。

int arr[]={0,0,0,1,0,1,0,1,0};
int lastz=7,i=0,temp,n;
n=9;
while(i<n){
        if(arr[i]==0 && i<lastz){
            lastz=i;
        } else if(arr[i]==1 && lastz<i){
            temp=arr[lastz];
            arr[lastz]=arr[i];
            arr[i]=temp;
            lastz++;
        }
        i++;
 }

Pratik Patil 8 年前

下面是C实现,它将在O(N)时间内给出解决方案。

/*
C program to sort a binary array in one pass
Input:  0 1 0 1 1 0
OutPut: 0 0 0 1 1 1
*/

#include<stdio.h>
void segregate0and1(int*, int);

int main()
{
    int a[] = {0, 1, 0, 1, 1, 0};
    int array_length = sizeof(a)/sizeof(a[0]);

    segregate0and1(a, array_length);

    printf("Array after segregation: ");
    for (int i = 0; i < array_length; i++)
        printf("%d ", a[i]);
    printf("\n");    

    return 0;
}

void segregate0and1(int a[], int array_length)
{
    int left = 0, right = array_length-1;

    while (left < right)
    {
        /* Increment left index while we see 0 at left */
        while (a[left] == 0 && left < right)
            left++;

        /* Decrement right index while we see 1 at right */
        while (a[right] == 1 && left < right)
            right--;

        /* If left is smaller than right then there is a 1 at left
          and a 0 at right.  Exchange a[left] and a[right]*/
        if (left < right)
        {
            a[left] = 0;
            a[right] = 1;
        }
    }
}