※ 引述《softwind (software everywhere)》之銘言：
: 你用 ch去查 一個特定 'B' 必定存在一組 也只能有一組 紀錄
: 用 prior = 1去查 結果亦同
: 所以 你用 "BROYGLPW" 和他的prior並行array <1,2,3,4,5,6,7,8>
: 來看 兩個是一樣的
: but 最大的差別是 {1,2,3,4,5,6,7,8} 是嚴格遞增 所以用 array
: 對回 ch 是 O(1)
: 但是 "BROYGLPW" 並不連續 所以頂多用我之前敲過的
這小事,只要寫個普通的對應程式,把字母對應為順序號碼:
enum Letter {
None = -1,
B = 0, R,
O, Y,
G, L,
P, W
};
enum Letter charToLetter(char ch) {
switch (ch) {
case 'B':
return B;
case 'R':
return R;
case 'O':
return O;
case 'Y':
return Y;
case 'G':
return G;
case 'L':
return L;
case 'P':
return P;
case 'W':
return W;
default:
return None;
}
}
雖然寫得很長,但就是 O(1) 程度,並且可以把不連續資料調整為連續資料.
然後在任何 sort 的 compare 函式會看到這樣的程式碼:
if ( charToLetter(a[i]) > charToLetter(a[j]) ) {
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
: compiling-time fixed array -> poweron-time qsort -> run-time bsearch
: 降到 O(logN)
: ---------------------------------------------------------------------
: 假設 你接一組 <'B',81> 用的是
: typedef struct{
: char ch;
: int value;
: }S_CHAR_VAL_PAIR;
: 字母比對 自行實作
: int getPrior_byChar( char ch ); //如果覺得麻煩 就用線性search吧
: cmp func:
: int cmp_byChVal( const void *pL, const void *pR){
: int pr1 = getPrior_byChar( ((S_CHAR_PRIOR_PAIR*)pL)->ch );
: int pr2 = getPrior_byChar( ((S_CHAR_PRIOR_PAIR*)pR)->ch );
: int res=0;
: if ( (res=pr1-pr2)!=0 )
: return res;
: return ((S_CHAR_PRIOR_PAIR*)pL)->value
: - ((S_CHAR_PRIOR_PAIR*)pR)->value;
: }
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.160.109.24
※ 編輯: yauhh 來自: 218.160.109.24 (06/24 04:31)