【8.04更新】上海华为的一道关于指针方面的编程题

我从网下下的一份华为笔试题大全里的题目：

int A[nSize]，其中隐藏着若干0，其余非0整数，写一个函数int Func(int* A, int nSize)，使A把0移至后面，非0整数移至 
数组前面并保持有序，返回值为原数据中第一个元素为0的下标。(尽可能不使用辅助空间且考虑效率及异常问题，注释规范且给出设计思路)

自己尝试做了下，以下是代码：

#include <iostream>
using namespace std;
/*
 * int A[nSize]，其中隐藏着若干0，其余非0整数，写一个函数int Func(int* A, int nSize)，使A把0移至后面，非0整数移至
 * 数组前面并保持有序，返回值为原数据中第一个元素为0的下标。(尽可能不使用辅助空间且考虑效率及异常问题，注释规范且给出设计思路)
 *
 */
int Func(int *A, int nSize) {
	int index = (nSize - 1);
	//由后往前
	while ((nSize--) >= 0) {
		if (*(A + nSize) == 0) {//为零，直接下标前移
			index = nSize;
			continue;
		}
		//否则拿前面的数据与自己相比较
		for (int i = 0; i < nSize; i++) {
			int last = *(A + nSize);
			int pre = *(A + i);
			if (pre == 0) {//直接交换,跳出for循环
				*(A + nSize) = pre;
				*(A + i) = last;
				index = nSize;
				break;
			}
			if (last > pre) {//排序交换
				*(A + nSize) = pre;
				*(A + i) = last;
				;//swap
			}
		}
	}
	return index;
}

int main(void) {
	const int intSize = 10;
	int A[intSize] = { 0, 4, 7, 2, 160, 0, 34, 21, 0, 19, 107 };
	cout << "The return value= " << Func(&A[0], intSize);
	return 0;
}

2010年5月20日更新：
优秀方案：
由第二页Turbo 编写
一个循环就搞掂了.

public static void main(String[] args) {   
    int[] a = { 0, 4, 7, 2, 160, 0, 34, 21, 0, 19, 107 };   
    int j = 0;   
    for (int i = 0; i < a.length; i++) {   
        if (a[i] == 0 && i != a.length - 1 && a[i + 1] != 0) {   
            a[j++] = a[i + 1];   
            a[i + 1] = 0;   
        }   
    }   
  
    System.out.println(Arrays.toString(a));   
}  

2010年8月4日更新：
Turbo 的代码确实有问题，如，将数组第一个元素置非1值，结果为[34, 21, 19, 107, 160, 0, 0, 0, 0, 0, 0]，显然不对，这是我的审核没到位，感谢liaohui0719提出！

liaohui0719 写道

Turbo的代码有个小瑕疵，若第一个元素不为零，则逻辑会出问题。

应为：
public static void main(String[] args) {     

       int[] a = { 7, 2, 160,0, 0, 34, 21, 0, 19, 0,0,0,107 };   
 
       int j = -1;     

       for (int i = 0; i < a.length; i++) {     

           if(j==-1 && a[i]==0)
           {
               j=i;
           }

           if (a[i] == 0 && i != a.length - 1 && a[i + 1] != 0) {    
               a[j++] = a[i + 1];     
               a[i + 1] = 0;     
           }

       }     
    
       System.out.println(Arrays.toString(a)); 
}  

评论

18 楼 liaohui0719 2010-08-02  

Turbo的代码有个小瑕疵，若第一个元素不为零，则逻辑会出问题。

应为：
public static void main(String[] args) {     

       int[] a = { 7, 2, 160,0, 0, 34, 21, 0, 19, 0,0,0,107 };   
 
       int j = -1;     

       for (int i = 0; i < a.length; i++) {     

           if(j==-1 && a[i]==0)
           {
               j=i;
           }

           if (a[i] == 0 && i != a.length - 1 && a[i + 1] != 0) {    
               a[j++] = a[i + 1];     
               a[i + 1] = 0;     
           }

       }     
    
       System.out.println(Arrays.toString(a)); 
}  

17 楼 benjiam 2010-07-21  

int[] a = { 0, 4, 7, 2, 160, 0, 34, 21, 0, 19, 107 };  
    int j = 0;
    int first = -1;
      
    for (int i = 0; i < a.length; ) {  
       if (a[i] == 0 )
       {
            if (first == -1)
            {
               first  = i;
            }
          i++;         
         
       }  else {
         a[j] = a[i];
         j++;
         i++;
        }
    } 
    for (; j < length; j++)
    {
       a[j] = 0;
    }

16 楼 benjiam 2010-07-21  

第二个算法是错误的
多个0 相近的情况

15 楼 Turbo 2010-05-20  

一个循环就搞掂了.

	public static void main(String[] args) {
		int[] a = { 0, 4, 7, 2, 160, 0, 34, 21, 0, 19, 107 };
		int j = 0;
		for (int i = 0; i < a.length; i++) {
			if (a[i] == 0 && i != a.length - 1 && a[i + 1] != 0) {
				a[j++] = a[i + 1];
				a[i + 1] = 0;
			}
		}

		System.out.println(Arrays.toString(a));
	}

14 楼 figure_he_he 2010-05-20  

<pre name="code" class="java"><pre name="code" class="java"> public static void maopao(int[] arra){

boolean flag=false;
int i=0;
int swap;
int length=arra.length-1;
boolean nozero=false;
boolean first=true;
int zeroIndex=-1;
while(i&lt;length){
int j=0;
nozero=true;
while(j&lt;arra.length-i-1){
if(arra[j]==0){
if(first){
first=false;
zeroIndex=j;
}
swap=arra[j+1];
arra[j+1]=arra[j];
arra[j]=swap;
nozero=false;

}
j++;

}
if(nozero){
break;
}
i++;
}
System.out.println(zeroIndex);

}</pre>
 </pre>
<p>冒泡实现：主要那个排序很难理解，按大小，还是原来顺序</p>

13 楼 pingqunnayang 2010-05-19  

<p>java实现</p>
<pre name="code" class="java"> static int z=0;
public static void main(String[] args){
int[] A={1,2,3,0,4,5,7,0,7,5,3,2,0,234,3,0,2,4};
// int len=A.length;
//     change(A,len-1);
// quickSort(A,0,A.length-1);
huawei(A);
    for(int a:A){
    System.out.print(a +",");
    }
   
}

public static void huawei(int[] array){
int len=array.length;
for(int i=0;i&lt;len;i++){
z++;
if(array[i]==0){
turns(array,i);
break;
}
}

}
public static void turns(int[] array,int i){
int len=array.length,temp;
int j=0;
for(;i&lt;len-1;i++){
                                 if(array[i+1]!=0){
           sort(array,i-j,i+1);
                }else{
          j++;
           }
}
}

public static void sort(int[] A,int i,int j){
int temp;
temp=A[i];
A[i]=A[j];
A[j]=temp;
    for(int a:A){
    }
}</pre>
<p> 17次  感觉还行</p>
<p> </p>
<p>1,2,3,4,0,5,7,0,7,5,3,2,0,234,3,0,2,4,<br>1,2,3,4,5,0,7,0,7,5,3,2,0,234,3,0,2,4,<br>1,2,3,4,5,7,0,0,7,5,3,2,0,234,3,0,2,4,<br>1,2,3,4,5,7,7,0,0,5,3,2,0,234,3,0,2,4,<br>1,2,3,4,5,7,7,5,0,0,3,2,0,234,3,0,2,4,<br>1,2,3,4,5,7,7,5,3,0,0,2,0,234,3,0,2,4,<br>1,2,3,4,5,7,7,5,3,2,0,0,0,234,3,0,2,4,<br>1,2,3,4,5,7,7,5,3,2,234,0,0,0,3,0,2,4,<br>1,2,3,4,5,7,7,5,3,2,234,3,0,0,0,0,2,4,<br>1,2,3,4,5,7,7,5,3,2,234,3,2,0,0,0,0,4,<br>1,2,3,4,5,7,7,5,3,2,234,3,2,4,0,0,0,0,</p>
<p>1,2,3,4,5,7,7,5,3,2,234,3,2,4,0,0,0,0,<br> </p>

12 楼 caravsapm70 2010-05-19  

<div class="quote_title">chinpom 写道</div>
<div class="quote_div">
<div class="quote_title">lzyzizi 写道</div>
<div class="quote_div">楼主的算法好复杂。。。<br><br>我是这样想的:根据要求选个排序算法，然后你只要做这样一个判断，就是当是数字0的时候的，他比任何数（包括）都要小，这样排序完0就到最后去了。</div>
<p>好像这样做是最好的，在Java中的话就是写个实现Compartor接口的类，不过就是在返回值的时候，需要遍历一下数组。</p>
<p> </p>
</div>
<p>c里面就是调用一下qsort就行了.</p>

11 楼 vaneng 2010-05-15  

	public static int A(int[] arr){
		int cur = 0;
		for(int i=0; i<arr.length; i++){
			if(arr[i]!=0)
				arr[cur++]=arr[i];
		}
		for(int i=cur; i<arr.length; i++){
			arr[i]=0;
		}
		return cur;
	}

10 楼 zzc_zj 2010-05-14  

<pre name="code" class="java"></pre>
<p>java希尔排序实现，借用了下arr[0],欢迎拍砖：<br>        <span style="white-space: pre;">package sort;</span></p>
<pre name="code" class="java">
import java.util.Random;

public class Test {

public static void main(String args[]){
Random random= new Random(6);
int[] arr = new int[6];
for(int i=1;i&lt;5;i++){
arr[i] = (int) (random.nextDouble()*100);
}
for(int i=1;i&lt;arr.length;i++){
System.out.print(arr[i]+" ");
}
System.out.println();
//insertSort(arr);
shellInsertSort(arr);
for(int i=1;i&lt;arr.length;i++){
System.out.print(arr[i]+" ");
}
System.out.println();
System.out.println("the position of first zero is :" + arr[0]);
}
private static void insertSort(int[] arr){
int firstZero = arr[0];
for(int i=2;i&lt;arr.length;i++){
if(firstZero == 0){
if(arr[i-1] == 0 )firstZero = i-1;
if(arr[i] == 0 )firstZero = i;
}
if(arr[i] &lt; arr[i-1]){
arr[0] = arr[i];
//arr[i] = arr[i-1];

int insertPos = 0;
for(int k=i-1;k&gt;=0;k--){
if(arr[k] &gt; arr[0]){
arr[k+1] = arr[k];
}else{
insertPos = k+1;
break;
}
}
arr[insertPos] = arr[0];
}
}
arr[0] = firstZero;
}

private static void shellInsertSort(int[] arr,int inc){
int firstZero = arr[0];//第一个元素记录的是数字0出现的位置
for(int i=inc+1;i&lt;arr.length;i++){
if(firstZero == 0){
if(arr[i] == 0)firstZero = i;
if(arr[i-inc] == 0)firstZero = i-inc;
}
if(arr[i] &lt; arr[i-inc]){
arr[0] = arr[i];

int insertPos = i;
for(int k=i-inc;k&gt;=0;k-=inc){
if(arr[k] &gt; arr[0]){
arr[k+inc] = arr[k];
if(k-inc &lt;= 0){
insertPos = k;
}
}else{
insertPos = k+inc;
break;
}
}
arr[insertPos] = arr[0];
}
}
arr[0] = firstZero;
}

private static void shellInsertSort(int[] arr){
int[] incs = {7,5,3,1};
for(int i=0;i&lt;incs.length;i++){
shellInsertSort(arr,incs[i]);
}
}
}
</pre>
 
<p> </p>

9 楼 treemanfm 2010-05-14  

keanu-re 写道

。。记下出现0的次数就行了吧。。。

正解，只需一次遍历，判断为0，直接拿后面第一个非0的数填充，非0数填充为0，遍历完了 0都移到最后了

package com.gpdi.strcom;

import com.gpdi.sort.*;

/**
 * @author Administrator
 *
 */
public class Test01 {
	
	private static  int [] DATA = {0,1,0,0,3,4,5,0,0,0,0,10,99,32754,0,0};
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		moveZero(DATA,DATA.length);
		for (int var : DATA	 ){
			System.out.println(var);
		}
	}
	
	
	private static void moveZero(int [] data,int size){
		for (int i =0 ; i<size; i++){
			while( 0 != data[i])
			{
				i++;
			}
			int j = i;
			while ((j<size)&&(0==data[j])) {
				j++;
			}
			if ((j>=i)&&(i<size)&&(j<size)) {
				SortUtil.sortSwap(data, i, j);
			}
		}
	}
}

8 楼 EldonReturn 2010-05-12  

不知道这个有序是啥意思
如果是保持原来的顺序的话，那就按照下面的来
如果是大小有序的话，那就先一遍两头遍历，把0放后面；然后再把前面非0的部分排个序。

int *p1, *p2;
p1 = p2 = A;
// 初始状态是p1和p2从第一个元素开始，p1移动到第一个0元素，p2移动到p1后第一个非0的元素
// 中间状态是p1指向第一个是0的元素，p2指向p1后第一个非零元素
// 比如 ....000000...02304.....
//          p1        p2
// 然后交换一下
// 结束时p2在数组末尾
// ......23000000.....000
//         p1           p2
// 这样一次遍历就够了
// 移动p1到第一个0值
while(p1 < A + nSize && *p1 != 0) p1++;
if(p1 == A + nSize) return;
p2 = p1;
while(p2 < A + nSize)
{
    // 移动p1到第一个0值
    while(p1 < A + nSize && *p1 != 0) p1++;
    if(p1 == A + nSize) return;
    // 移动p2到p1后的第一个非0值
    while(p2 < A + nSize && *p2 == 0) p2++;
    if(p2 == A + nSize) return;
    // 交换一下位置
    *p1 = *p2;
    *p2 = 0;
}

7 楼 keanu-re 2010-05-12  

需要这么折腾么。。

6 楼 keanu-re 2010-05-12  

。。记下出现0的次数就行了吧。。。

5 楼 mathfox 2010-05-12  

用两个指针，第一个指向0，第二个向后走，P1 != P2 就向前移，一次遍历就完了，

不过可能移的数据比较多。

这个效率怎么样

4 楼 chandler 2010-05-12  

<div class="quote_title">chinpom 写道</div>
<div class="quote_div">
<div class="quote_title">lzyzizi 写道</div>
<div class="quote_div">楼主的算法好复杂。。。<br><br>我是这样想的:根据要求选个排序算法，然后你只要做这样一个判断，就是当是数字0的时候的，他比任何数（包括）都要小，这样排序完0就到最后去了。</div>
<p>好像这样做是最好的，在Java中的话就是写个实现Compartor接口的类，不过就是在返回值的时候，需要遍历一下数组。</p>
<p> </p>
</div>
<p><br>     就会java的觉得这里Compartor接口也可以用。怎么说呢。java的Compartor接口就是比较大小。排序有jdk负责。我的思路是写两个函数。</p>
<p>     一个<span class="datatypes"><strong><span style="color: #2e8b57;">int</span></strong></span><span> Func(</span><span class="datatypes"><strong><span style="color: #2e8b57;">int</span></strong></span><span> *A, </span><span class="datatypes"><strong><span style="color: #2e8b57;">int</span></strong></span><span> nSize) 只负责排序。一个 compare方法。负责排序的具体实现。这样可能好很多。</span></p>

3 楼 lzyzizi 2010-05-12  

<div class="quote_title">chinpom 写道</div>
<div class="quote_div">
<div class="quote_title">lzyzizi 写道</div>
<div class="quote_div">楼主的算法好复杂。。。<br><br>我是这样想的:根据要求选个排序算法，然后你只要做这样一个判断，就是当是数字0的时候的，他比任何数（包括）都要小，这样排序完0就到最后去了。</div>
<p>好像这样做是最好的，在Java中的话就是写个实现Compartor接口的类，不过就是在返回值的时候，需要遍历一下数组。</p>
<p> </p>
</div>
<p> </p>
<p>不用遍历也行~ 只要在比较的时候记录下0的数量就行了。</p>

2 楼 chinpom 2010-05-11  

<div class="quote_title">lzyzizi 写道</div>
<div class="quote_div">楼主的算法好复杂。。。<br><br>我是这样想的:根据要求选个排序算法，然后你只要做这样一个判断，就是当是数字0的时候的，他比任何数（包括）都要小，这样排序完0就到最后去了。</div>
<p>好像这样做是最好的，在Java中的话就是写个实现Compartor接口的类，不过就是在返回值的时候，需要遍历一下数组。</p>
<p> </p>

1 楼 lzyzizi 2010-05-11  

楼主的算法好复杂。。。

我是这样想的:根据要求选个排序算法，然后你只要做这样一个判断，就是当是数字0的时候的，他比任何数（包括）都要小，这样排序完0就到最后去了。