人人校招筆試題
---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)
題解:(轉載請聯系博主,個人看法,僅供參考!)
1、給定一個有序數組a,長度為len,和一個數X,判斷A數組裡面是否存在兩個數,他們的和為X,bool judge(int *a, int len, int x),存在返回true,不存在返回false
解: 注意仔細研究題目中的條件,比如關鍵的一句,有序數組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:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int Judge(int *a, int len, int x)
{
int Ascending = 0;//為1表示升序,否則降序
Ascending = a[1] > a[0] ? 1 : 0;
int *CopyA = (int *)malloc(sizeof(int) * len);
memset(CopyA, 0, sizeof(int) * len);
//構建另一數組
int icount = 0;
for(icount = 0; icount < len; icount++)
{
CopyA[icount] = x - a[icount];
}
//比較兩個指針移動的值,這裡用索引代替指針
int i = len - 1, j = 0;
while(i >= 0 && j < len)
{
if(a[i] > CopyA[j])
{
switch(Ascending)
{
case 0: j++; break;//降序
case 1: i--; break;//升序
default:break;
}
}
else if(a[i] == CopyA[j])
{
return 1;
}
else
{
switch(Ascending)
{
case 0: i--; break;//降序
case 1: j++; break;//升序
default:break;
}
}
}
return 0;
}
int main()
{
int a[] = {59,41,21,10,5};
int len = 5;
int x = 190;
switch(Judge(a, len, x))
{
case 0: printf("%d isn't exist!", x);break;
case 1: printf("%d is exist!", x);break;
default : break;
}
return 0;
}
接下來請看第2頁精彩內容:http://www.linuxidc.com/Linux/2013-10/90814p2.htm