# 其他高效技巧 ## two pointers 利用問題本身與序列的特性，使用兩個下標 i,j 對序列進行掃描，以較低的復雜度解決問題。 典型的應用有歸并排序和快速排序。 ## 打表 打表是典型的用空間換時間的技巧，常見用法有 - 在程序中一次性計算出所有需要的結果，之后直接查詢取值 - 在 B 程序中分一次或多次計算所有需要的結果，手工把結果寫在 A 程序的數組中，然后在 A 程序中可直接使用。例如，n 皇后問題 - 對于想不出算法的題目，先用暴力程序計算小范圍數據的結果，然后找蛛絲馬跡 ## 活用遞推 例如，有幾個 PAT 的題目，找每個 A 左側的 P 和右側的 T ## 隨機選擇算法 ```C++ // 隨機選擇算法，從遞增序列 a[left, right] 中返回第 K 小的數 int randSelect(int a[], int left, int right, int K){ if(left==right) return a[left]; // 遞歸邊界 // p 為 A[left] 在 a[left, right] 中的位置 int p=partition(a,left,right); // p 是 在 a[left, right] 第 M 小的數 int M=p-left+1; if(K==M) return a[p]; if(K<M) return randSelect(a,left,p-1,K); else return randSelect(a,p+1,right,M-K); } ``` ## ChangeLog > 2018.09.03 初稿