銆愬惎绋嬩箣鏃咃細绠楁硶杩涢樁涔嬭矾銆?/p>
鏈枃灏嗗紩棰嗘偍韪忎笂涓€娈典粠鍩虹鍒拌繘闃剁殑绠楁硶瀛︿範涔嬫梾銆備粠鍥為【鍩虹姒傚康寮€濮嬶紝鐩磋嚦澶嶆潅绠楁硶鐨勫垎鏋愪笌浼樺寲锛屽叏闈㈡兜鐩栨暟鎹粨鏋勩€佺畻娉曞鏉傚害鍒嗘瀽銆侀珮鏁堟帓搴忎笌鏌ユ壘鎶€宸т互鍙婂浘绠楁硶鍏ラ棬銆傞€氳繃鐢熷姩瀹炵敤鐨勬寚鍗楋紝鍔╂偍閫愭鎻愬崌绠楁硶瀛︿範涔嬫梾鐨勫眰娆°€?/p>
涓€銆佹暟鎹粨鏋勭殑濂ョ
璁╂垜浠繁鍏ヤ簡瑙ｆ暟鎹粨鏋勭殑鍩烘湰姒傚康銆傛暟缁勩€侀摼琛ㄣ€佹爤銆侀槦鍒楀拰鏍戠瓑鏁版嵁缁撴瀯锛岄兘鏄畻娉曞涔犱腑鐨勯噸瑕佺粍鎴愰儴鍒嗐€?/p>
鏁扮粍锛氱敤浜庡瓨鍌ㄤ竴缁勮繛缁厓绱狅紝濡?arr = [1, 2, 3, 4, 5]銆?/p>
閾捐〃锛氶€氳繃鑺傜偣鍔ㄦ€佸瓨鍌ㄦ暟鎹紝姣忎釜鑺傜偣鍖呭惈鍊煎拰鎸囧悜涓嬩竴涓妭鐐圭殑鎸囬拡銆?/p>
鏍堬細浣跨敤鍒楄〃瀹炵幇鏍堝姛鑳斤紝閫氳繃 stack.append(1) 鍘嬫爤鍜?stack.pop() 寮规爤銆?/p>
闃熷垪锛氬疄鐜板厛杩涘厛鍑猴紙FIFO锛夌壒鎬х殑鏁版嵁缁撴瀯锛岄€氳繃 queue.append(1) 鍏ラ槦鍜?queue.popleft() 鍑洪槦銆?/p>
鏍戯細濡備簩鍙夋爲锛屾瘡涓妭鐐瑰寘鍚€间互鍙婂乏瀛╁瓙鑺傜偣鍜屽彸瀛╁瓙鑺傜偣銆?/p>
浜屻€佺畻娉曞鏉傚害鍒嗘瀽鐨勯噸瑕佹€?/h3>
鐞嗚В绠楁硶鐨勬晥鐜囨槸绠楁硶瀛︿範鐨勫叧閿€傛椂闂村鏉傚害鎻忚堪绠楁硶鎵ц鏃堕棿涓庤緭鍏ュぇ灏忕殑鍏崇郴锛岃€岀┖闂村鏉傚害鍏虫敞绠楁硶杩愯鏃舵墍闇€鐨勯澶栧唴瀛樸€傛帉鎻″ぇO琛ㄧず娉曪紝鑳藉娓呮櫚鍦拌〃绀虹畻娉曟墽琛屾椂闂存垨绌洪棿闇€姹傜殑澧為暱鐜囷紝濡?O(1)锛堝父鏁版椂闂达級銆丱(n)锛堢嚎鎬ф椂闂达級绛夈€?/p>
涓夈€佸疄渚嬩唬鐮佽В鏋愶細璁＄畻鏁扮粍骞冲潎鍊肩殑鏃堕棿涓庣┖闂村鏉傚害
浠ヤ笅绀轰緥浠ｇ爜灞曠ず浜嗗浣曡绠椾竴涓暟缁勭殑骞冲潎鍊硷細
```python
def average(arr):
return sum(arr) / len(arr)
example_arr = [1, 2, 3, 4, 5]
average_value = average(example_arr)
print("骞冲潎鍊间负:", average_value)
```
姝や唬鐮佺殑鏃堕棿澶嶆潅搴︿负O(n)锛屽叾涓璶涓烘暟缁勭殑闀垮害銆傜┖闂村鏉傚害涓篛(1)锛屽洜涓洪櫎浜嗚緭鍏ユ暟缁勫锛屾病鏈変娇鐢ㄩ澶栫殑绌洪棿銆傞€氳繃鍒嗘瀽涓嶅悓绠楁硶鐨勬椂闂村鏉傚害鍜岀┖闂村鏉傚害锛屾垜浠彲浠ヨ瘎浼板畠浠殑鏁堢巼锛屽苟鍦ㄧ畻娉曡璁′腑杩涜浼樺寲銆?/p>
鍥涖€佽繄鍚戣繘闃讹細鎺屾彙鏍稿績鎶€鑳?/h3>
鏈枃鍏ㄩ潰娑电洊浜嗘暟鎹粨鏋勫拰绠楁硶鐨勫熀纭€鐭ヨ瘑锛岄€氳繃瀹炰緥浠ｇ爜灞曠ず浜嗘瘡涓€姝ョ殑瀹炵幇涓庡簲鐢ㄣ€傚湪姝ゅ熀纭€涓婏紝鎮ㄥ皢鑳藉娣卞叆鐞嗚В绠楁硶杩涢樁鐨勬牳蹇冩妧鑳斤紝涓烘湭鏉ョ殑绠楁硶瀛︿範鍜屽簲鐢ㄥ瀹氬潥瀹炲熀纭€銆?/p>
缁х画鎺㈢储绠楁硶棰嗗煙鐨勮繘闃剁煡璇嗭紝涓嶆柇鎸戞垬鑷垜锛屾偍灏嗛€愭笎鎴愰暱涓虹畻娉曢鍩熺殑浣间郊鑰呫€傛帓搴忎笌鏌ユ壘绠楁硶鐨勬繁搴︽帰璁?/p>
鍦ㄧ紪绋嬬殑涓栫晫閲岋紝鎺掑簭鍜屾煡鎵炬槸涓ょ鍩烘湰鐨勬搷浣滐紝瀹冧滑璐┛濮嬬粓锛屽嚑涔庢秹鍙婂埌鎵€鏈夋暟鎹鐞嗗満鏅€傝鎴戜滑涓€璧锋帰璁ㄦ帓搴忕畻娉曞拰鏌ユ壘绠楁硶鐨勬繁搴︾煡璇嗐€?/p>
鎺掑簭绠楁硶娣卞叆瑙ｆ瀽
鎺掑簭绠楁硶鏄暟鎹鐞嗕腑鐨勪竴椤归噸瑕佹妧鏈€傚揩閫熸帓搴忎綔涓轰竴绉嶉珮鏁堢殑鎺掑簭绠楁硶锛屽叾宸ヤ綔鍘熺悊鏄€庢牱鐨勫憿锛熻鎴戜滑閫氳繃浠ｇ爜绀轰緥鏉ユ繁鍏ョ悊瑙ｃ€?/p>
浠ｇ爜绀轰緥锛氬疄鏂藉揩閫熸帓搴?/p>
```python
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2] 閫夊彇涓棿鍏冪礌浣滀负鍩哄噯鍊?/p>
left = [x for x in arr if x < pivot] 灏嗗皬浜庡熀鍑嗗€肩殑鍏冪礌鏀惧叆宸﹁竟鍒楄〃
middle = [x for x in arr if x == pivot] 灏嗙瓑浜庡熀鍑嗗€肩殑鍏冪礌鍗曠嫭瀛樻斁
right = [x for x in arr if x > pivot] 灏嗗ぇ浜庡熀鍑嗗€肩殑鍏冪礌鏀惧叆鍙宠竟鍒楄〃
return quick_sort(left) + middle + quick_sort(right) 瀵瑰乏鍙充袱杈瑰垪琛ㄩ€掑綊鎺掑簭锛屽苟鍚堝苟缁撴灉
```
閫氳繃姝や唬鐮侊紝鎴戜滑鍙互鐪嬪埌蹇€熸帓搴忔槸閫氳繃閫夋嫨涓€涓熀鍑嗗€煎皢鏁扮粍鍒掑垎涓轰笁涓儴鍒嗭紝鐒跺悗閫掑綊鍦板宸﹀彸涓ら儴鍒嗚繘琛屽悓鏍风殑鎿嶄綔锛屾渶缁堝疄鐜版暣涓暟缁勭殑鎺掑簭銆傝繖鏄竴绉嶅垎娌荤瓥鐣ョ殑搴旂敤銆?/p>
鏌ユ壘绠楁硶杩涢樁瀛︿範
瀵逛簬鏌ユ壘鎿嶄綔锛屾垜浠彲浠ヤ粠鍩虹鐨勭嚎鎬ф煡鎵惧拰浜屽垎鏌ユ壘寮€濮嬶紝鐒跺悗娣卞叆浜嗚В鍝堝笇琛ㄥ拰鏍戠粨鏋勭殑搴旂敤銆傚搱甯岃〃涓烘垜浠彁渚涗簡涓€绉嶄互杩戜箮甯告暟鏃堕棿杩涜鏌ユ壘鐨勬柟寮忥紝鑰屾爲缁撴瀯鍒欏彲浠ヤ紭鍖栨暟鎹殑缁勭粐鏂瑰紡锛屾彁楂樻煡鎵炬晥鐜囥€?/p>
鍦ㄥ疄闄呭簲鐢ㄤ腑锛岄€夋嫨浣曠鏌ユ壘绠楁硶鍙栧喅浜庡叿浣撳満鏅拰闇€姹傘€備緥濡傦紝褰撴暟鎹噺杈冨ぇ涓旈渶瑕侀绻佹煡璇㈡椂锛屽搱甯岃〃寰€寰€鏄竴涓洿濂界殑閫夋嫨锛涜€屽綋鏁版嵁闇€瑕佷繚鎸佹湁搴忔椂锛屾爲缁撴瀯濡備簩鍙夋悳绱㈡爲鍒欐洿涓洪€傜敤銆?/p>
---
浠ｇ爜绀轰緥锛氭瀯寤哄搱甯岃〃鐨勫熀鐭?/p>
璁╂垜浠紑濮嬫帰绱㈠搱甯岃〃鐨勫ゥ绉橈紒杩欐槸涓€涓潪甯稿熀纭€涓斿疄鐢ㄧ殑鏁版嵁缁撴瀯銆?/p>
```python
class HashTable:
def __init__(self, size=1024):
self.size = size
self.table = [[[] for _ in range(size)] for _ in range(size)] 涓轰綍閫夋嫨浜岀淮鍒楄〃浣滀负鍒濆鍊煎憿锛熶笅鏂囧皢涓烘偍鎻檽銆?/p>
def _hash(self, key): 鍝堝笇鍑芥暟锛岀敤浜庤绠楅敭鍊肩殑瀛樺偍浣嶇疆銆傚畠鏄搱甯岃〃鐨勬牳蹇冦€?/p>
return hash(key) % self.size 浣跨敤妯¤繍绠楃‘淇濋敭鍊煎缁堝湪鍝堝笇琛ㄨ寖鍥村唴銆?/p>
hash_key = self._hash(key) 璁＄畻閿€肩殑鍝堝笇鍊笺€?/p>
for item in self.table[hash_key]: 鍦ㄥ搴旂殑鍝堝笇妲戒腑鏌ユ壘鏄惁瀛樺湪鐩稿悓鐨勯敭銆傚鏋滃瓨鍦紝鍒欐洿鏂板€硷紱鍚﹀垯锛屾坊鍔犳柊鐨勯敭鍊煎銆?/p>
if item[0] == key:
item[1] = value
return
self.table[hash_key].append([key, value]) 鑻ヤ笉瀛樺湪锛屽垯鍦ㄥ搴旀Ы涓坊鍔犳柊鐨勯敭鍊煎銆?/p>
def get(self, key): 閫氳繃閿幏鍙栧€肩殑鏂规硶銆傚搱甯岃〃鐨勯瓍鍔涘湪浜庡叾楂樻晥鐨勬煡鎵鹃€熷害銆傝繖鏄浣曞疄鐜扮殑锛熷綊鍔熶簬鍝堝笇鍑芥暟鍜岄珮鏁堢殑瀛樺偍缁撴瀯銆?/p>
hash_key = self._hash(key) 璁＄畻閿€肩殑鍝堝笇鍊笺€?/p>
for item in self.table[hash_key]: 鍦ㄥ搴旂殑鍝堝笇妲戒腑鏌ユ壘閿€煎銆?/p>
if item[0] == key:
return item[1]
return None 鑻ユ湭鎵惧埌锛屽垯杩斿洖None銆?杩欏氨鏄搱甯岃〃鏌ユ壘鎿嶄綔鐨勯瓍鍔涙墍鍦紒
```
鐜板湪璁╂垜浠皾璇曚竴涓嬪浣曚娇鐢ㄨ繖涓搱甯岃〃锛?/p>
```python
hash_table = HashTable() 鍒涘缓鍝堝笇琛ㄥ疄渚嬨€?浣犲彲浠ヨ缃笉鍚岀殑鍒濆澶у皬鏉ヨ瀵熷叾鎬ц兘鍙樺寲鍝︼紒 馃槈 |
