人们校招笔试题

2013-10-01

人人校招笔试题人人校招笔试题---9月22日，人人校招笔试题1、给定一个有序数组a，长度为len，和一个数X，判断A

人人校招笔试题

人人校招笔试题

---9月22日，人人校招笔试题

1、给定一个有序数组a，长度为len，和一个数X，判断A数组里面是否存在两个数，他们的和为X，bool judge(int *a, int len, int x)，存在返回true，不存在返回false

2、给定有n个数的数组a，其中超过一半的数为一个定值，在不进行排序、不开设额外数组的情况下，以最高效的算法找到这个数：int find(int *a, int n)

题解：(转载请联系博主，个人看法，仅供参考！)

解：注意仔细研究题目中的条件，比如关键的一句，有序数组a，这是一个有序的数组，这一点十分重要！

思路1：遍历，时间复杂度为O(N2)，很显然，这种方法没什么实际意义，而且题目中说了这个一个有序数组，采用遍历的方法是你想不出其他解法时的最坏选择而已！

思路2：根据有序数组的特点，要么递增要么递减，这个时候我们不要凭空想象，拿出纸和笔，举一个实例来分析是最好的方法，

人们校招笔试题

　　算法的思路通过上图可以清晰的表现出来，这里再简单叙述一下：申请一个与原数组a[N]一样长度的内存空间arr[N]，用给定的值X减去原数组中的元素，对应的放到申请的内存空间arr[N]中，设置两个指针p和q，分别指向原数组a[N]的最后一个元素和arr[N]的第一个元素，指针移动满足条件：

指针移动必须满足条件：p和q指针没有越界，越界则跳出

　　若指针指向的值相等，则返回true；

　　若原数组是升序的，那么每次移动指向的值较大的指针；

　　若原数组是降序的，那么每次移动指向的值较小的指针；

移动结束，跳出移动指针的循环，说明不存在，返回false

这道题目其实可以不用那么复杂，这个算法使用了O（N）的空间，另一个较好算法是：设置两个指针，指向首尾的位置，指向的值分别为a，b，判断a + b 与x的大小关系来移动指针，当a + b > x时，移动a，b中较大值的指针；当a + b = x时，返回true；当a + b < x时，移动a，b中较小值的指针！

code：


code：
#include <stdio.h>#include <stdlib.h>int find(int *a, int n){    int VeryNum = 0;    int cnt = 0;    int i = 0;    for(i = 0; i < n; i++)    {        if(cnt == 0)        {            VeryNum = a[i];            cnt = 1;        }        else        {            if(a[i] == VeryNum)            {                cnt++;            }            else            {                cnt--;            }        }    }    return VeryNum;}int main(void){    int a[] = {15, 15, 5, 15, 5, 15, 1};    int n = 7;    printf("%d\n", find(a, n));    return 0;}

题目部分摘取自july CSDN网站：http://blog.csdn.net/v_july_v/article/details/11921021 

注：1.本文版权归作者和CSDN所有，未经允许不得转载，侵权必究！
2.本博客与博客园上的博客为同一博客主：http://www.cnblogs.com/bestDavid/

热点排行

编程

人们校招笔试题