2014人人网算法类笔试题汇总

　　如下为大家汇总的内容是2014年人人网算法类笔试题，感兴趣的朋友可以练习下。

　　1.给出一个有序数组啊，长度为len，另外给出第三个数X，问是否能在数组中找到两个数，这两个数之和等于第三个数X。

　　我们首先看到第一句话，这个数组是有序的，所以，我们可以定义两个指针，一个指向数组的第一个元素，另一个指向应该指向的位置(这个需要看具体的实现和数组给定的值)，首先计算两个位置的和是否等于给定的第三个数，如果等于则算法结束，如果大于，则尾指针向头指针方向移动，如果小于，则头指针向尾指针方向移动，当头指针大于等于尾指针时算法结束，没有找到这样的两个数。

　　解法一：

　　#include

　　int judge(int *a, int len, int k, int *num1, int *num2);

　　int main(int argc, char **argv)

　　{

　　int test_array[] = {3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16};

　　int result = -1;

　　int num1, num2;

　　result = judge(test_array, sizeof(test_array) / sizeof(int), 12, &num1, &num2);

　　if(result == 0)

　　{

　　printf("%d %d ", num1, num2);

　　}

　　else if(result == -1)

　　{

　　printf("can't find");

　　}

　　else

　　{

　　printf("error");

　　}

　　}

　　int judge(int *a, int len, int k, int *num1, int *num2)

　　{

　　int *low = NULL;

　　int *high = NULL;

　　int i = 0;

　　int result = -1;

　　if(a == NULL || len < 2)

　　{

　　return result;

　　}

　　if(a[0] >= k)

　　{

　　return result;

　　}

　　while(a[i] <= k && i < len)

　　{

　　i++;

　　}

　　low = a;

　　high = a + i - 1;

　　while(low < high)

　　{

　　*num1 = *low;

　　*num2 = *high;

　　if((*low + *high) == k)

　　{

　　result = 0;

　　break;

　　}

　　else if((*low + *high) > k)

　　{

　　high--;

　　}

　　else if((*low + *high) < k)

　　{

　　low++;

　　}

　　}

　　return result;

　　}

　　解法二：

　　#include

　　using namespace std;

　　int hash_table[100];

　　bool judge(int *a, int len, int x)

　　{

　　memset(hash_table, 0, sizeof(hash_table));

　　for (int i=0; i

　　{

　　hash_table[x - a[i]] = 1;

　　}

　　for (int i=0; i

　　{

　　if (hash_table[i] == 1)

　　{

　　return true;

　　}

　　}

　　return false;

　　}

　　int main()

　　{

　　int len = 10;

　　int a[10] = {1, 3, 5, 7, 9, 4, 2, 8, 10, 6};

　　int x = 19;

　　if (judge(a, len, x))

　　{

　　cout<<"Yes"<

　　}

　　else

　　{

　　cout<<"No"<

　　}

　　system("pause");

　　return 0;

　　}

　　本题解决方法：hash table。

　　时间复杂度：O(N)

　　空间复杂度：O(N)

　　2.给定有n个数的数组a，其中有超过一半的数为一个定值，在不进行排序，不开设额外数组的情况下，以最高效的算法找出这个数。

　　int find(int* a, int n);

　　#include

　　using namespace std;

　　int find(int *a, int n)

　　{

　　int t = a[0];

　　int count = 0;

　　for (int i=0; i

　　{

　　if (count == 0)

　　{

　　t = a[i];

　　count = 1;

　　continue;

　　}

　　else

　　{

　　if (a[i] == t)

　　{

　　count++;

　　}

　　else

　　{

　　count--;

　　}

　　}

　　}

　　return t;

　　}

　　int main()

　　{

　　int n = 10;

　　int a[10] = {1, 3, 2, 3, 3, 4, 3, 3, 3, 6};

　　cout<

　　system("pause");

　　return 0;

　　}

　　Time Complexity: O(n)

　　Space Complexity:O(1)





更多热门的笔试题目推荐：
中国人民银行的笔试题

广东北电研发工程师笔试题
金融投资顾问常考笔试题目