人人網(wǎng)算法類筆試題和面試題答案匯總

　　如下為大家匯總的內(nèi)容是2017年人人網(wǎng)算法類筆試題，感興趣的朋友可以練習(xí)下。
　　1.給出一個有序數(shù)組啊，長度為len，另外給出第三個數(shù)X，問是否能在數(shù)組中找到兩個數(shù)，這兩個數(shù)之和等于第三個數(shù)X。

　　我們首先看到第一句話，這個數(shù)組是有序的，所以，我們可以定義兩個指針，一個指向數(shù)組的第一個元素，另一個指向應(yīng)該指向的位置(這個需要看具體的實現(xiàn)和數(shù)組給定的值)，首先計算兩個位置的和是否等于給定的第三個數(shù)，如果等于則算法結(jié)束，如果大于，則尾指針向頭指針方向移動，如果小于，則頭指針向尾指針方向移動，當(dāng)頭指針大于等于尾指針時算法結(jié)束，沒有找到這樣的兩個數(shù)。

　　解法一：

　　#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。

　　時間復(fù)雜度：O(N)

　　空間復(fù)雜度：O(N)

　　2.給定有n個數(shù)的數(shù)組a，其中有超過一半的數(shù)為一個定值，在不進(jìn)行排序，不開設(shè)額外數(shù)組的情況下，以最高效的算法找出這個數(shù)。

　　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) 更多熱門的筆試題目推薦：
中國人民銀行的筆試題
上海東方傳媒集團(tuán)筆試題
廣東北電研發(fā)工程師筆試題
金融投資顧問�？脊P試題目