lostpencil 阅读(1113) 评论(8)
题目:有一个数组里面里面的元素是0和非0的整数字混排,希望进行排序后所有的0放在数组前端,所有非0数字顺序不变放在数组后端.(主要考思维吧)
要求:
1,不能增加新的缓存(也就是不能用另外的数组或者字符串等结构来存储中间结果).
2,只能用一次单循环.


分析:1,因为上述两个要求,则只能在循环到每个元素的时候就把它放到正确的位置.
   2,对于结果数组来说,有效的是非0数和其顺序,0没有意义.
   3,按照常规思维来做其实不是很好想,虽然感觉答案就在眼前但是始终不好确定,特别是在面试这种相对有点压力的情况下(考官眼巴巴的望着你,根本就不好意思想很久),换另外一个题“非0数放前面,0放后面”就简单的多了。
算法:判断当次循环的数,非0的话就移动到非零数个数的位置,然后将这个数赋0,0就不用管了。
解答:假设数组arr[length],定义一个变量a,记录当前循环所遇见的非0数的个数,
a=0;
for(i=0;i<length;i++){
  if(0!=arr[i]){
           arr[a] = arr[i];
           arr[i] = 0;
            ++a;
  }
}
这样比较简单的思维就搞定了,非0放后面的话无非就是数组的反序循环了.
点评:感觉题目难就难在很难想到要反序循环数组,紧张的情况下思维也没有这么明了,容易按常规乱试,感觉就快出来了,但是始终有点不对。
(我当时是急发汗了)

评论列表
pcasa
re: 最近的面试题之数组排序
从后往前算
int a[LEN];
int k=LEN;
for(int i=LEN-1; i>=0; i--)
{
   if(a[i])
   {
      a[--k]=a[i];
      a[i]=0;
   }
}
第三方
re: 最近的面试题之数组排序
在下没有想出来,很惭愧
tt
re: 最近的面试题之数组排序
int low=0;
int high=length-1;
while(low<high)

  if(!a[low])
  {
    ++low;
    continue;
  }
  if(a[high])
  {
    --high;
    continue;
  }
  int temp=a[low];
  a[high]=a[low];
  a[low]=temp;
}
Desert Wolf
re: 最近的面试题之数组排序
int last = length -1;
for (int i=length-1;i--;i<=0)
{
    if (a[i] != 0 && i != last)
    {
         a[last--] = a[i];
         a[i] = 0;
    }
}
tester
re: 最近的面试题之数组排序
做下单元测试,发现各位都有些问题,楼主是顺序不对哦,我特讨厌笔试,
程序要能纸上写对,那调试器干什么的
#include <stdio.h>
#define LEN 4
int main(int argc, char* argv[])
{

int a[LEN] = {0,1,0,3};//测试用例 
#if 0 //1
int k=LEN; 
int i =0;
for(i = 0; i < LEN; i++)
{
printf("%d\n", a[i]);
}
for(i=LEN-1; i>=0; i--) 

if(a[i]) 

a[--k]=a[i]; 
a[i]=0; 

}
#endif
#if 0 //2
int i = 0;
int last = LEN -1; 
for (i=LEN-1;i--;i<=0) 

if (a[i] != 0 && i != last) 

a[last--] = a[i]; 
a[i] = 0; 

}
#endif
#if 1
int point = LEN-1;
int i = 0;
for(i = LEN -1; i > 0; i--)
{
if(0 != a[i])
{
if(i != point)
{
    a[point] = a[i];
    a[i] = 0;
}
point--;
}
}
#endif
#if 0 //3
int i = 0;
int low=0; 
int high=LEN-1; 
while(low<high) 
{  
if(!a[low]) 

++low; 
continue; 

if(a[high]) 

--high; 
continue; 

int temp=a[low]; 
a[high]=a[low]; 
a[low]=temp; 
}
#endif
#if 0 //4
int i = 0;
int ab = 0;
int length = LEN;
for(i=0;i<length;i++){
if(0!=a[i]){
           a[ab] = a[i];
           a[i] = 0;
            ++ab;
}
}

#endif
for(i = 0; i < LEN; i++)
{
printf("%d\n", a[i]);
}

printf("Hello World!\n");
return 0;
}

lostpencil
re: 最近的面试题之数组排序
我的代码是就是反序的,主要用来说明思路

发表评论
切换编辑模式