ä¸ãå «å¤§æåºç®æ³çæ»ä½æ¯è¾
äºãç®æ³åèªçç¹ç¹ï¼å ·ä½å®ç°è§åé¢å客ï¼
1.å¿«æ
ï¼1ï¼ç®æ³ææ³
éæ©ä¸ä¸ªåºåå ç´ ï¼å°æ¯åºåå ç´ å°çå ç´ æ¾å¨å ¶åé¢ï¼æ¯åºåå ç´ å¤§çå ç´ æ¾å¨å ¶åé¢ï¼ç¶åå¨å°å°äºåºåå¼å ç´ çåæ°åå大äºåºåå ç´ çåæ°åæåæ¥çæ¹æ³æåºï¼ç´å°æ´ä¸ªåºåæåº;
ï¼2ï¼ä¼ç¼ºç¹
ä¼ç¹ï¼æå¿«æ°æ®ç§»å¨å°ï¼
缺ç¹ï¼ä¸ç¨³å®ï¼
ï¼3ï¼æçåæ
æ¤æåºç®æ³çæçå¨åºåè¶ä¹±çæ¶åï¼æçè¶é«ãå¨æ°æ®æåºæ¶ï¼ä¼éåæå泡æåºï¼
ï¼4ï¼å¯¹äºåºåçéæ©
a.ä¸æ°åä¸
å ·ä½ææ³ï¼å¯¹å¾ æåºåºåä¸lowãmidãhighä¸ä¸ªä½ç½®ä¸æ°æ®è¿è¡æåºï¼åä»ä»¬ä¸é´çé£ä¸ªæ°æ®ä½ä¸ºæ¢è½´ï¼å¹¶ç¨0ä¸æ å ç´ åå¨æ¢è½´ï¼
b.éæºéååºå
å¼å ¥åå ï¼å¨å¾ æåºåæ¯é¨åæåºæ¶ï¼åºå®éåæ¢è½´ä½¿å¿«ææçä½ä¸ï¼
å ·ä½ææ³ï¼åå¨å¾ æåºåä¸ä»»æä¸ä¸ªå ç´ ä½ä¸ºåºåï¼
ï¼5ï¼ä¼åæ¹æ³
a.å½å¾ æåºåºåçé¿åº¦åå²å°ä¸å®å¤§å°åï¼ä½¿ç¨æå ¥æåºï¼
åå ï¼å¯¹äºå¾å°åé¨åæåºçæ°ç»ï¼å¿«æä¸å¦ææ好ãå½å¾ æåºåºåçé¿åº¦åå²å°ä¸å®å¤§å°åï¼ç»§ç»åå²çæçæ¯æå ¥æåºè¦å·®ï¼æ¤æ¶å¯ä»¥ä½¿ç¨ææèä¸æ¯å¿«æï¼
b.å¨ä¸æ¬¡åå²ç»æåï¼å¯ä»¥æä¸keyç¸ççå ç´ èéå¨ä¸èµ·ï¼ç»§ç»ä¸æ¬¡åå²æ¶ï¼ä¸å¿ å对äºkeyç¸çå ç´ åå²ï¼
ï¼6ï¼åºç¨åºæ¯
a.æ±æ°ç»ä¸ç¬¬kå°çæ°
å°æ°ç»ä¸æä¸ä¸ªå ç´ mä½ä¸ºååä¾æ®,å³m=arr[0]ãè¥måé¢çå ç´ ä¸ªæ°å¤§äºkï¼å第kå°çæ°ä¸å®å¨måé¢çå ç´ ä¸ï¼è¿æ¶æ们åªéè¦ç»§ç»å¨måé¢çå ç´ ä¸æ¾ç¬¬kå°çæ°ï¼è¥måé¢çå ç´ å°äºkï¼å第kå°çæ°ä¸å®å¨måé¢çå ç´ ä¸ï¼è¿æ¶æ们åªéè¦å¨måé¢çå ç´ ä¸æ¾ç¬¬kå°çæ°ï¼
2.å泡æåº
ï¼1ï¼åºæ¬åç
å¨è¦æåºçä¸ç»æ°ä¸ï¼å¯¹å½åè¿æªæ好åºçèå´å çå ¨é¨æ°ï¼èªä¸èä¸å¯¹ç¸é»ç两个æ°ä¾æ¬¡è¿è¡æ¯è¾ï¼è®©è¾å¤§çæ°å¾ä¸æ²ï¼è¾å°çå¾ä¸åãå³ï¼æ¯å½ä¸¤ç¸é»çæ°æ¯è¾ååç°ä»ä»¬çæåºä¸æåºè¦æ±ç¸åæ¶ï¼å°±å°ä»ä»¬äºæ¢ã
ï¼2ï¼ä¼ç¼ºç¹
ä¼ç¹ï¼ç¨³å®
缺ç¹ï¼æ ¢ï¼æ¯æ¬¡åªè½ç§»å¨ä¸¤ä¸ªç¸é»çæ°æ®ï¼
3.æå ¥æåº
ï¼1ï¼åºæ¬ææ³
å°ä¸ä¸ªè®°å½æå ¥å°å·²æåºå¥½çæåºè¡¨ä¸ï¼ä»èå¾å°ä¸ä¸ªæ°çï¼è®°å½æ°å¢1çæåºè¡¨ãå³å å°åºåç第ä¸ä¸ªè®°å½çææ¯ä¸ä¸ªæåºçååºåï¼ç¶åä»ç¬¬äºä¸ªè®°å½é个è¿è¡æå ¥ï¼ç´è³æ´ä¸ªåºåæåºä¸ºæ¢ã
ï¼2ï¼ä¼ç¼ºç¹
ä¼ç¹ï¼ç¨³å®ï¼å¿«
缺ç¹ï¼æ¯è¾æ¬¡æ°ä¸ä¸å®ï¼æ¯è¾æ¬¡æ°è¶å°ï¼æå ¥ç¹åçæ°æ®ç§»å¨è¶å¤ï¼ç¹å«æ¯æ°æ®éåºå¤§çæ¶å
4.å æåº
4.1ãäºåå å®ä¹ï¼
äºåå æ¯å®å ¨äºåæ æè¿ä¼¼å®å ¨äºåæ ãäºåå 满足两个ç¹æ§:
ï¼1ï¼ç¶ç»ç¹çé®å¼æ»æ¯å¤§äºæè çäºï¼å°äºæè çäºï¼ä»»ä½ä¸ä¸ªåèç¹çé®å¼ï¼
ï¼2ï¼æ¯ä¸ªç»ç¹çå·¦åæ åå³åæ é½æ¯ä¸ä¸ªäºåå ï¼
å½ç¶ç»ç¹çé®å¼æ»æ¯å¤§äºæè çäºä»»ä½ä¸ä¸ªåèç¹çé®å¼æ¶ä¸ºå¤§æ ¹å ãå½ç¶ç»ç¹çé®å¼æ»æ¯å°äºæçäºä»»ä½ä¸ä¸ªåèç¹çé®å¼æ¶ä¸ºå°æ ¹å ï¼
4.2ãå çåå¨ï¼
ä¸è¬é½ç¨æ°ç»æ¥è¡¨ç¤ºå ï¼iç»ç¹çç¶ç»ç¹ä¸æ 就为ï¼i-1ï¼/2.å®çå·¦å³åèç¹çä¸æ åå«ä¸º2*i+1å2*i+2.
4.3ãå çæå ¥ï¼
æ¯æ¬¡æå ¥é½æ¯å°æ°æ°æ®æ¾å¨æ°ç»æåãå¯ä»¥åç°ä»è¿ä¸ªæ°æ°æ®çç¶ç»ç¹å°æ ¹ç»ç¹å¿ ç¶ä¸ºä¸ä¸ªæåºçæ°åï¼ç¶åå°è¿ä¸ªæ°æ°æ®æå ¥å°è¿ä¸ªæåºæ°æ®ä¸
ï¼1ï¼ç¨å¤§æ ¹å æåºçåºæ¬ææ³
å å°åå§æ°ç»å»ºæä¸ä¸ªå¤§æ ¹å ï¼æ¤å¯¹ä¸ºåå§çæ åºåºï¼
åå°æ大çå ç´ åæ åºåºçæåä¸ä¸ªè®°å½äº¤æ¢ï¼ç±æ¤å¾å°æ°çæ åºåºåæåºåºï¼ä¸æ»¡è¶³<=çå¼ï¼
ç±äºäº¤æ¢åæ°çæ ¹å¯è½è¿åå æ§è´¨ï¼æ å°å½åæ åºåºè°æ´ä¸ºå ãç¶åå次å°å ¶ä¸æ大çå ç´ å该åºé´çæåä¸ä¸ªè®°å½äº¤æ¢ï¼ç±æ¤å¾å°æ°çæ åºåºåæåºåºï¼ä¸ä»æ»¡è¶³å ³ç³»çå¼<=çå¼ï¼åæ ·è¦å°å ¶è°æ´ä¸ºå ï¼
..........
ç´å°æ åºåºåªæä¸ä¸ªå ç´ ä¸ºæ¢ï¼
4.4ï¼åºç¨
寻æ¾M个æ°ä¸çåK个æå°çæ°å¹¶ä¿ææåºï¼
æ¶é´å¤æ度ï¼O(K)[å建K个å ç´ æ大å çæ¶é´å¤æ度] +ï¼M-Kï¼*log(K)[对å©ä½M-K个æ°æ®è¿è¡æ¯è¾å¹¶æ¯æ¬¡å¯¹æ大å è¿è¡ä»æ°æ大å å]
5.å¸å°æåº
ï¼1ï¼åºæ¬ææ³
å å°æ´ä¸ªå¾ æåºå ç´ åºååå²æè¥å¹²ååºåï¼ç±ç¸éæ个âå¢éâçå ç´ ç»æçï¼åå«è¿è¡ç´æ¥æå ¥æåºï¼ç¶åä¾æ¬¡ç¼©åå¢éåè¿è¡æåºï¼å¾ æ´ä¸ªåºåä¸çå ç´ åºæ¬æåºï¼å¢é足å¤å°ï¼æ¶ï¼åå¯¹å ¨ä½å ç´ è¿è¡ä¸æ¬¡ç´æ¥æå ¥æåºï¼å 为ç´æ¥æå ¥æåºå¨å ç´ åºæ¬æåºçæ åµä¸ï¼æçå¾é«ï¼ï¼
ï¼2ï¼éç¨åºæ¯
æ¯è¾å¨å¸å°æåºä¸æ¯æ主è¦çæä½ï¼èä¸æ¯äº¤æ¢ãç¨å·²ç¥æ好çæ¥é¿åºåçå¸å°æåºæ¯ç´æ¥æå ¥æåºè¦å¿«ï¼çè³å¨å°æ°ç»ä¸æ¯å¿«éæåºåå æåºè¿å¿«ï¼ä½å¨æ¶å大éæ°æ®æ¶å¸å°æåºè¿æ¯ä¸å¦å¿«æï¼
6.å½å¹¶æåº
ï¼1ï¼åºæ¬ææ³
é¦å å°åå§åºåçn个记å½çææ¯n个æåºçååºåï¼æ¯ä¸ªååºåçé¿åº¦ä¸º1ï¼ç¶å两两å½å¹¶ï¼å¾å°n/2个é¿åº¦ä¸º2çæåºååºåï¼å¨æ¤åºç¡ä¸ï¼å对é¿åº¦ä¸º2çæåºååºåè¿è¡ä¸¤ä¸¤å½å¹¶ï¼å¾å°è¥å¹²ä¸ªé¿åº¦ä¸º4çæåºååºåï¼ä»¥æ¤ç±»æ¨ï¼ç´å°å¾å°ä¸ä¸ªé¿åº¦ä¸ºnçæåºåºå为æ¢ï¼
ï¼2ï¼éç¨åºæ¯
è¥nè¾å¤§ï¼å¹¶ä¸è¦æ±æåºç¨³å®ï¼åå¯ä»¥éæ©å½å¹¶æåºï¼
7.ç®åéæ©æåº
ï¼1ï¼åºæ¬ææ³
第ä¸è¶ï¼ä»ç¬¬ä¸ä¸ªè®°å½å¼å§ï¼å°åé¢n-1个记å½è¿è¡æ¯è¾ï¼æ¾å°å ¶ä¸æå°çè®°å½å第ä¸ä¸ªè®°å½è¿è¡äº¤æ¢ï¼
第äºè¶ï¼ä»ç¬¬äºä¸ªè®°å½å¼å§ï¼å°åé¢n-2个记å½è¿è¡æ¯è¾ï¼æ¾å°å ¶ä¸æå°çè®°å½å第2个记å½è¿è¡äº¤æ¢ï¼
...........
第iè¶ï¼ä»ç¬¬i个记å½å¼å§ï¼å°åé¢n-i个记å½è¿è¡æ¯è¾ï¼æ¾å°å ¶ä¸æå°çè®°å½å第i个记å½è¿è¡äº¤æ¢ï¼
以æ¤ç±»æ¨ï¼ç»è¿n-1è¶æ¯è¾ï¼å°n-1个记å½æå°ä½ï¼å©ä¸ä¸ä¸ªæ大记å½ç´æ¥æå¨æåï¼