算法问题

Question

同事问的一道面试题。现有数组0,1,0,1,0,1,1,0 用最快的方式，将0全部移到数组的前面，1全部移到数组后面。
結果为:0,0,0,0,1,1,1,1以下为我的做法，不知道对不对
int main(int argc, char** argv) {
    int array[]={0,1,0,1,0,1,1,0};
    int i,j,k;
    
    i=0;
    j=7;
    while(j>i)
    {
        if(array[i]>array[j])
        {
            k=array[i];
            array[i]=array[j];
            array[j]=k;
        }        if (array[j]==1) j--;
        if (array[i]==0) i++;
    }    for(i=0;i<=7;i++) printf("%d\n",array[i]);
    
    return (EXIT_SUCCESS);
}

Answer 1

using System;class Program
{
  static void Main()
  {
    int[] a = {0,1,0,1,0,1,1,0};
    int n = 0;
    foreach (int x in a) n += x;
    int i = 0;
    for (; i < a.Length - n; i++) a[i] = 0;
    for (; i < a.Length; i++) a[i] = 1;
    foreach (int x in a) Console.WriteLine(x);
  }
}

Answer 2

把你的两个 if 改为 while 可能会更快：
using System;class Program
{
  static void Main()
  {
    int[] a = {0,1,0,1,0,1,1,0};    int i, j, k;
    i = 0;
    j = 7;
    while (j > i)
    {
      if (a[i] > a[j])
      {
        k = a[i];
        a[i] = a[j];
        a[j] = k;
      }
      while (a[j] == 1) j--; // <--- 这里的 while 原先是 if
      while (a[i] == 0) i++; // <--- 这里的 while 原先是 if
    }    foreach (int x in a) Console.WriteLine(x);
  }
}

Answer 3

把交换 a[i]、a[j] 改为直接赋值 a[i] = 0; a[j] = 1; 会更快些：
using System;class Program
{
  static void Main()
  {
    int[] a = {0,1,0,1,0,1,1,0};    int i, j;
    i = 0;
    j = a.Length - 1;
    while (j > i)
    {
      if (a[i] > a[j])
      {
        a[i] = 0;            // <--- 这样更快！
        a[j] = 1;            // <--- 这样更快！
      }
      while (a[j] == 1) j--; // <--- 这里的 while 原先是 if
      while (a[i] == 0) i++; // <--- 这里的 while 原先是 if
    }    foreach (int x in a) Console.WriteLine(x);
  }
}

Answer 4

int array[]={0,1,0,1,0,1,1,0,1};
int size = sizeof(array)/sizeof(int);
int count=0;
for( int i=0;i<size;i++)
{
count +=array[i];
}
memset(array,0,(size-count)*sizeof(int));
for(int j=size-count;j<size;j++)
{
array[j]=1;
}
return 0;

Answer 5

    for(int j=size-count;j<size;j++)
    {
        array[j]=1;
    }// 是不是可以改为：    memset(array + size - count, 1, count * sizeof(int));

Answer 6

考虑了一下，不行，sizeof(char) 和 sizeof(int) 不一样。

Answer 7

array + size - count 应为 array + (size - count) * sizeof(int)

Answer 8

   memset(array + size - count, 1, count * sizeof(int));
不行,memset是按字节走

Answer 9

if (sizeof(wchar_t) == sizeof(int)) wmemset(array + size - count, 1, count);
else for (int j = size - count; j < size; j++) array[j] = 1;

Answer 10

static void Main(string[] args)
        {            
            int[] array = {0,1,0,1,0,1,1,0};            
            List<int> aList = array.ToList();
            aList.Sort();
            array = aList.ToArray();            
        }

Answer 11

int main(int argc, char** argv) {
int array[]={0,1,0,1,0,1,1,0};
int iend0, iproc;
for( int i = 0; i < sizeof(array)/sizeof(int); i++ )
{
if( array[i] )
{
end0 = i;
break;
}
} for( int i = end0 + 1; i < sizeof(array)/sizeof(int); i++ )
{
if( !array[i] )
{
iproc = i;
break;
}
} for( int i = iproc; i < sizeof(array)/sizeof(int); i++ )
{
if( !array[i] )
{
array[iend0++] = 0;
array[i] = 1;
}
}
for(i=0;i<=7;i++) printf("%d\n",array[i]); return (EXIT_SUCCESS);
}循环一次，第3个循环不会对元素产生重复的0/1值判断