題目：輸入一個(gè)已經(jīng)按升序排序過的數(shù)組和一個(gè)數(shù)字，在數(shù)組中查找兩個(gè)數(shù)，使得它們的和正好是輸入的那個(gè)數(shù)字。要求時(shí)間復(fù)雜度是O(n)。如果有多對數(shù)字的和等于輸入的數(shù)字，輸出任意一對即可。
例如輸入數(shù)組1、2、4、7、11、15和數(shù)字15。由于4+11=15，因此輸出4和11。
分析：如果我們不考慮時(shí)間復(fù)雜度，最簡單想法的莫過去先在數(shù)組中固定一個(gè)數(shù)字，再依次判斷數(shù)組中剩下的n-1個(gè)數(shù)字與它的和是不是等于輸入的數(shù)字�？上н@種思路需要的時(shí)間復(fù)雜度是O(n2)。
我們假設(shè)現(xiàn)在隨便在數(shù)組中找到兩個(gè)數(shù)。如果它們的和等于輸入的數(shù)字，那太好了，我們找到了要找的兩個(gè)數(shù)字;如果小于輸入的數(shù)字呢?我們希望兩個(gè)數(shù)字的和再大一點(diǎn)。由于數(shù)組已經(jīng)排好序了，我們是不是可以把較小的數(shù)字的往后面移動(dòng)一個(gè)數(shù)字?因?yàn)榕旁诤竺娴臄?shù)字要大一些，那么兩個(gè)數(shù)字的和也要大一些，就有可能等于輸入的數(shù)字了;同樣，當(dāng)兩個(gè)數(shù)字的和大于輸入的數(shù)字的時(shí)候，我們把較大的數(shù)字往前移動(dòng)，因?yàn)榕旁跀?shù)組前面的數(shù)字要小一些，它們的和就有可能等于輸入的數(shù)字了。
我們把前面的思路整理一下：最初我們找到數(shù)組的第一個(gè)數(shù)字和最后一個(gè)數(shù)字。當(dāng)兩個(gè)數(shù)字的和大于輸入的數(shù)字時(shí)，把較大的數(shù)字往前移動(dòng);當(dāng)兩個(gè)數(shù)字的和小于數(shù)字時(shí)，把較小的數(shù)字往后移動(dòng);當(dāng)相等時(shí)，打完收工。這樣掃描的順序是從數(shù)組的兩端向數(shù)組的中間掃描。
問題是這樣的思路是不是正確的呢?這需要嚴(yán)格的數(shù)學(xué)證明。感興趣的讀者可以自行證明一下。
參考代碼：
///////////////////////////////////////////////////////////////////////
// Find two numbers with a sum in a sorted array
// Output: ture is found such two numbers, otherwise false
///////////////////////////////////////////////////////////////////////
bool FindTwoNumbersWithSum
(
int data[], // a sorted array
unsigned int length, // the length of the sorted array
int sum, // the sum
int& num1, // the first number, output
int& num2 // the second number, output
)
{
bool found = false;
if(length < 1)
return found;
int ahead = length - 1;
int behind = 0;
while(ahead > behind)
{
long long curSum = data[ahead] + data[behind];
// if the sum of two numbers is equal to the input
// we have found them
if(curSum == sum)
{
num1 = data[behind];
num2 = data[ahead];
found = true;
break;
}
// if the sum of two numbers is greater than the input
// decrease the greater number
else if(curSum > sum)
ahead --;
// if the sum of two numbers is less than the input
// increase the less number
else
behind ++;
}
return found;
}
-查找鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)
題目：輸入一個(gè)單向鏈表，輸出該鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)。鏈表的倒數(shù)第0個(gè)結(jié)點(diǎn)為鏈表的尾指針。鏈表結(jié)點(diǎn)定義如下：
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
分析：為了得到倒數(shù)第k個(gè)結(jié)點(diǎn)，很自然的想法是先走到鏈表的尾端，再從尾端回溯k步。可是輸入的是單向鏈表，只有從前往后的指針而沒有從后往前的指針。因此我們需要打開我們的思路。
既然不能從尾結(jié)點(diǎn)開始遍歷這個(gè)鏈表，我們還是把思路回到頭結(jié)點(diǎn)上來。假設(shè)整個(gè)鏈表有n個(gè)結(jié)點(diǎn)，那么倒數(shù)第k個(gè)結(jié)點(diǎn)是從頭結(jié)點(diǎn)開始的第n-k-1個(gè)結(jié)點(diǎn)(從0開始計(jì)數(shù))。如果我們能夠得到鏈表中結(jié)點(diǎn)的個(gè)數(shù)n，那我們只要從頭結(jié)點(diǎn)開始往后走n-k-1步就可以了。如何得到結(jié)點(diǎn)數(shù)n?這個(gè)不難，只需要從頭開始遍歷鏈表，每經(jīng)過一個(gè)結(jié)點(diǎn)，計(jì)數(shù)器加一就行了。
這種思路的時(shí)間復(fù)雜度是O(n)，但需要遍歷鏈表兩次。第一次得到鏈表中結(jié)點(diǎn)個(gè)數(shù)n，第二次得到從頭結(jié)點(diǎn)開始的第n-k-1個(gè)結(jié)點(diǎn)即倒數(shù)第k個(gè)結(jié)點(diǎn)。
如果鏈表的結(jié)點(diǎn)數(shù)不多，這是一種很好的方法。但如果輸入的鏈表的結(jié)點(diǎn)個(gè)數(shù)很多，有可能不能一次性把整個(gè)鏈表都從硬盤讀入物理內(nèi)存，那么遍歷兩遍意味著一個(gè)結(jié)點(diǎn)需要兩次從硬盤讀入到物理內(nèi)存。我們知道把數(shù)據(jù)從硬盤讀入到內(nèi)存是非常耗時(shí)間的操作。我們能不能把鏈表遍歷的次數(shù)減少到1?如果可以，將能有效地提高代碼執(zhí)行的時(shí)間效率。
如果我們在遍歷時(shí)維持兩個(gè)指針，第一個(gè)指針從鏈表的頭指針開始遍歷，在第k-1步之前，第二個(gè)指針保持不動(dòng);在第k-1步開始，第二個(gè)指針也開始從鏈表的頭指針開始遍歷。由于兩個(gè)指針的距離保持在k-1，當(dāng)?shù)谝粋�(gè)(走在前面的)指針到達(dá)鏈表的尾結(jié)點(diǎn)時(shí)，第二個(gè)指針(走在后面的)指針正好是倒數(shù)第k個(gè)結(jié)點(diǎn)。
這種思路只需要遍歷鏈表一次。對于很長的鏈表，只需要把每個(gè)結(jié)點(diǎn)從硬盤導(dǎo)入到內(nèi)存一次。因此這一方法的時(shí)間效率前面的方法要高。
思路一的參考代碼：
///////////////////////////////////////////////////////////////////////
// Find the kth node from the tail of a list
// Input: pListHead - the head of list
// k - the distance to the tail
// Output: the kth node from the tail of a list
///////////////////////////////////////////////////////////////////////
ListNode* FindKthToTail_Solution1(ListNode* pListHead, unsigned int k)
{
if(pListHead == NULL)
return NULL;
// count the nodes number in the list
ListNode *pCur = pListHead;
unsigned int nNum = 0;
while(pCur->m_pNext != NULL)
{
pCur = pCur->m_pNext;
nNum ++;
}
// if the number of nodes in the list is less than k
// do nothing
if(nNum < k)
return NULL;
// the kth node from the tail of a list
// is the (n - k)th node from the head
pCur = pListHead;
for(unsigned int i = 0; i < nNum - k; ++ i)
pCur = pCur->m_pNext;
return pCur;
}
思路二的參考代碼：
///////////////////////////////////////////////////////////////////////
// Find the kth node from the tail of a list
// Input: pListHead - the head of list
// k - the distance to the tail
// Output: the kth node from the tail of a list
///////////////////////////////////////////////////////////////////////
ListNode* FindKthToTail_Solution2(ListNode* pListHead, unsigned int k)
{
if(pListHead == NULL)
return NULL;
ListNode *pAhead = pListHead;
ListNode *pBehind = NULL;
for(unsigned int i = 0; i < k; ++ i)
{
if(pAhead->m_pNext != NULL)
pAhead = pAhead->m_pNext;
else
{
// if the number of nodes in the list is less than k,
// do nothing
return NULL;
}
}
pBehind = pListHead;
// the distance between pAhead and pBehind is k
// when pAhead arrives at the tail, p
// Behind is at the kth node from the tail
while(pAhead->m_pNext != NULL)
{
pAhead = pAhead->m_pNext;
pBehind = pBehind->m_pNext;
}
return pBehind;
}
討論：這道題的代碼有大量的指針操作。在軟件開發(fā)中，錯(cuò)誤的指針操作是大部分問題的根源。因此每個(gè)公司都希望程序員在操作指針時(shí)有良好的習(xí)慣，比如使用指針之前判斷是不是空指針。這些都是編程的細(xì)節(jié)，但如果這些細(xì)節(jié)把握得不好，很有可能就會(huì)和心儀的公司失之交臂。
另外，這兩種思路對應(yīng)的代碼都含有循環(huán)。含有循環(huán)的代碼經(jīng)常出的問題是在循環(huán)結(jié)束條件的判斷。是該用小于還是小于等于?是該用k還是該用k-1?由于題目要求的是從0開始計(jì)數(shù)，而我們的習(xí)慣思維是從1開始計(jì)數(shù)，因此首先要想好這些邊界條件再開始編寫代碼，再者要在編寫完代碼之后再用邊界值、邊界值減1、邊界值加1都運(yùn)行一次(在紙上寫代碼就只能在心里運(yùn)行了)。
擴(kuò)展：和這道題類似的題目還有：輸入一個(gè)單向鏈表。如果該鏈表的結(jié)點(diǎn)數(shù)為奇數(shù)，輸出中間的結(jié)點(diǎn);如果鏈表結(jié)點(diǎn)數(shù)為偶數(shù)，輸出中間兩個(gè)結(jié)點(diǎn)前面的一個(gè)。
