笔试算法题汇总"/>
人人网2014笔试算法题汇总
1.给出一个有序数组啊,长度为len,另外给出第三个数X,问是否能在数组中找到两个数,这两个数之和等于第三个数X。
我们首先看到第一句话,这个数组是有序的,所以,我们可以定义两个指针,一个指向数组的第一个元素,另一个指向应该指向的位置(这个需要看具体的实现和数组给定的值),首先计算两个位置的和是否等于给定的第三个数,如果等于则算法结束,如果大于,则尾指针向头指针方向移动,如果小于,则头指针向尾指针方向移动,当头指针大于等于尾指针时算法结束,没有找到这样的两个数。
解法一:
#include <stdio.h> 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\t%d\n", 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 <iostream> 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<len; ++i) { hash_table[x - a[i]] = 1; } for (int i=0; i<len; ++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"<<endl; } else { cout<<"No"<<endl; } system("pause"); return 0;
}
本题解决方法:hash table。
时间复杂度:O(N)
空间复杂度:O(N)
2.给定有n个数的数组a,其中有超过一半的数为一个定值,在不进行排序,不开设额外数组的情况下,以最高效的算法找出这个数。
int find(int* a, int n);
#include <iostream> using namespace std; int find(int *a, int n)
{ int t = a[0]; int count = 0; for (int i=0; i<n; ++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<<find(a, n)<<endl; system("pause"); return 0;
}
Time Complexity: O(n)
Space Complexity:O(1)
转载请注明原创链接:
更多推荐
人人网2014笔试算法题汇总
发布评论