华为面试题——一道关于指针方面的编程题(C/C++)

    int A[nSize],其中隐藏着若干0,其余非0整数,写一个函数int Func(int* A, int nSize),使A把0移至后面,非0整数移至数组前面并保持有序,返回值为原数据中第一个元素为0的下标。

    尽可能不使用辅助空间且考虑效率及异常问题,注释规范且给出设计思路

    注:我的方法的复杂度为O(n),大家如果有其它方法希望可以交流一下。

/*
     Blog:
  http://blog.csdn.net/jiangxinnju
 
 */
 #include <iostream>
 #include <random>
using namespace std;
#define ARRAYSZIE 100
 int Func(int* A,int nSize)
 {
     int *p_zero = A; //指向最开始的零值
     int *p_unzero = A; //指向最后的非零值
     while(1)
     {
         for(int i=(p_zero-A); i<nSize; i++)
         {
             if(A[i] == 0) //找到第一个零值
             {
                 p_zero = &A[i];
                 break;
             }
             if(i == nSize-1) //没有找到零值,说明全部为非零值
             {
                 return -1;
             }
         }
        for(int i=(p_zero-A+1); i<nSize; i++)
         {
             if(A[i] != 0) //找到零值之后的第一个非零值
             {
                 p_unzero = &A[i];
                 break;
             }
             if(i == nSize-1) //没有找到下一个非零值,说明全部为零值,或者已经排序完毕
             {
                 return (p_zero-A);
             }
         }
        *p_zero = *p_unzero;
         *p_unzero = 0;
         p_zero++;
     }
 }
 void test_exercise001()
 {
     int A[ARRAYSZIE];
     default_random_engine e;
     uniform_int_distribution<> d(0,1);
     for(int i=0; i<ARRAYSZIE; i++)
     {
         A[i] = d(e); //随机产生0和1值
     }
     for(int i=0; i<ARRAYSZIE; i++)
     {
         cout << A[i] << " ";
     }
     cout << "\nThe position of the first zero is: " << Func(A,ARRAYSZIE) << endl;
     for(int i=0; i<ARRAYSZIE; i++)
     {
         cout << A[i] << " ";
     }
 }
 

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器之心

入门 | 一文带你了解Python集合与基本的集合运算

了解 Python 集合: 它们是什么,如何创建它们,何时使用它们,什么是内置函数,以及它们与集合论操作的关系

13630
来自专栏数据结构与算法

洛谷P3273 [SCOI2011]棘手的操作

题目描述 有N个节点,标号从1到N,这N个节点一开始相互不连通。第i个节点的初始权值为a[i],接下来有如下一些操作:U x y: 加一条边,连接第x个节点和第...

33470
来自专栏微信公众号:Java团长

Java泛型详解

定义了一个List类型的集合,先向其中加入了两个字符串类型的值,随后加入一个Integer类型的值。这是完全允许的,因为此时list默认的类型为Object类型...

11920
来自专栏一直在跳坑然后爬坑

RxJava2操作符之“Scan”作用示例用法运行结果分析总结

扫描,遍历,用法和上一个Reduce操作符差不多,只是这个操作符会将每一个过程的中间产物发射出来,而不是只发射结果

10330
来自专栏大闲人柴毛毛

剑指 offer——面试题8求旋转数组的最小值

题目:将一个非递减序列的某一处切一刀,再把前半段序列放到后半段序列的后面,这样组成的新序列叫做“旋转数组”。要求获取一个旋转数组的最小值。 这本质上是一个求最值...

36160
来自专栏数据结构与算法

06:整数奇偶排序

06:整数奇偶排序 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 给定10个整数的序列,要求对其重新排序。排序要求: 1...

40260
来自专栏HansBug's Lab

1212: [HNOI2004]L语言

1212: [HNOI2004]L语言 Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 643  Solved...

30250
来自专栏xingoo, 一个梦想做发明家的程序员

快速排序

算法思想:对于输入的子数组a[p:r],按下面三个步骤: 1 分解:以a[p]为基准元素将a[p:r]分成三段,a[p:q-1],a[q],a[q+1:r],使...

21590
来自专栏desperate633

LintCode 排颜色 II题目分析代码

给定一个有n个对象(包括k种不同的颜色,并按照1到k进行编号)的数组,将对象进行分类使相同颜色的对象相邻,并按照1,2,...k的顺序进行排序。

10520
来自专栏韦弦的偶尔分享

Swift 两数之和 - LeetCode

12020

扫码关注云+社区

领取腾讯云代金券