人人校招筆試題
---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
