2013人人网校园招聘技术笔试题

网校园招聘技术笔试题"/>

2013人人网校园招聘技术笔试题

1. 给定有n 个数的数组 a ，其中超过一半的数为一个定值，在不进行排序、不开设额外数组的情况下，以最高效的算法找出这个数： int find （ int * a ， int n ）
int find_ch( int * a , int n)
{
    int count = 1 , i;
    int ans = a [ 0 ];
    for( i = 1; i <n; i ++)
    {
        if( a [ i ] != ans)
          count --;
        if( count == 0)
        {
            ans = a [ i ];
            count ++;
        }
        else
            count ++;
    }
    return ans;
}
//有个数字出现的次数超过了数组长度的一半，也就是有个数字出现的次数比其他所有数字出现的次数的和 //还要多。遍历数组时保存连个值，一个是数组中的数字，一个是出现的次数，遍历到一个数字时，如果该数字和之前保存的数字相同，则次数加1，如果不同，则次数减1，如果次数为0，则遍历下一个数组元素，并把次数设置为1. 2.给定一个有序数组a，长度为len，和一个数X，判断A数组里面是否存在两个数，它们的和为X，   bool judge（int *a，int len，int x）,存在返回true，不存在返回false
#include<iostream>
using namespace std;
bool judge( int * a , int len , int x)
{
    int i , left , right , middle;
    for( i = 0; i < len; i ++)
    {
        left = i;
        right = len - 1;
        while( left <= right)
        {
            middle =( left + right) / 2;
            if( a [ middle ] == x - a [ i ])
                return true;
            else if( a [ middle ] < x - a [ i ])
                left = middle + 1;
            else if( a [ middle ] > x - a [ i ])
                right = middle - 1;
        }
    }
    return false;
}
int main()
{
    int ch [ 7 ] = { - 3 , - 1 , 0 , 11 , 14 , 21 , 30 };
    int a;
    while( cin >> a)
    {
        if( judge( ch , 7 , a))
            cout << "yes" << endl;
        else
            cout << "no" << endl;
    }
    return 0;
}
//先取一个数组元素x[i]，然后二分查找X-x[i]是否在数组中。