簡述 快排是排序算法中繞不開的關(guān)鍵一環(huán)，其中涉及到分治算法，二分查找等關(guān)鍵知識。 本文內(nèi)容： 快排原理 代碼實(shí)現(xiàn) 分區(qū)過程圖示 <啊哈算法> 中的另一種實(shí)現(xiàn) 復(fù)雜度 優(yōu)化 快...
發(fā)簡信
IP屬地：浙江
-
-
遞歸時(shí)間復(fù)雜度 推演計(jì)算遞歸的時(shí)間復(fù)雜度計(jì)算較為麻煩。以下我們使用歸并排序的例子，對遞歸復(fù)雜度進(jìn)行推演。 假設(shè)現(xiàn)在有一個(gè)歸并排序。他的運(yùn)行總時(shí)間是 T（n），我們通過將其分解成 2 個(gè)計(jì)算式，即 ：...
-
兩個(gè)有序的鏈表合并題目描述： 具體如下圖： 即，將 L1 和 L2 鏈表進(jìn)行合并。 思路1：遞歸 每次比較 l1 和 val 和 l2 的 val，誰小，就繼續(xù)循環(huán)他的 next 節(jié)遞歸進(jìn)行比...
-
鏈表中環(huán)的檢測
題目描述： 這里考察的也是快慢指針。 當(dāng)然，如果我們用 HashSet ，也可以實(shí)現(xiàn)。當(dāng)時(shí)明顯不是這道題的考察目的。 我們假設(shè)，使用 2 個(gè)指針，快指針是慢指針的 2 倍速。...
-
求鏈表的中間節(jié)點(diǎn)題目描述： 這題考察的也是快慢指針。 我們對偶數(shù)和奇數(shù)分別進(jìn)行分析： 當(dāng)鏈表是偶數(shù)時(shí)，我們需要判斷他自身是否為 null，如果為 null，說明到了末尾。 當(dāng)鏈表是奇數(shù)時(shí)，我...
-
刪除鏈表中倒數(shù)第 n 個(gè)節(jié)點(diǎn)引言 題目描述： 簡單說，這道題的的公式就是：(length - n + 1).next = (length - n).next;即，將 n 的 pre 節(jié)點(diǎn)的 next 節(jié)...
-
單鏈表反轉(zhuǎn)
鏈表題中，鏈表反轉(zhuǎn)應(yīng)該是出現(xiàn)頻率最高的一道題。 如何實(shí)現(xiàn)？ 我們分析一下，一個(gè)鏈表，【1， 2，3，4，5】，反轉(zhuǎn)成 【5，4，3，2，1】，我們可以適應(yīng)循環(huán)。 循環(huán)的過程中...
-
隊(duì)列的 2 種實(shí)現(xiàn)方式
引言 隊(duì)列，是一個(gè)線性表，和數(shù)組，棧，鏈表類似。隊(duì)列和棧類似，戲稱“邊吃邊拉”。即 FIFO。 隊(duì)列和棧還有一個(gè)不同，棧只需維護(hù)一個(gè)棧頂指針，而隊(duì)列需要維護(hù) 2 個(gè)指針，隊(duì)首...
-
棧的應(yīng)用前述 棧，戲稱“邊吃邊拉”。 棧是一種“操作受限” 的數(shù)據(jù)結(jié)構(gòu)，只有 push 和 pop 兩種操作。先進(jìn)先出，后勁后出。 可以由數(shù)組實(shí)現(xiàn)，也可以是鏈表實(shí)現(xiàn)，前者稱之為 順序...
-
平均時(shí)間復(fù)雜度簡述 在數(shù)據(jù)結(jié)構(gòu)與算法中，“時(shí)間復(fù)雜度”表示“隨著數(shù)據(jù)規(guī)模的增長，他的增長趨勢”，而時(shí)間復(fù)雜度，通過細(xì)化，可以分為：最好時(shí)間復(fù)雜度，最壞時(shí)間復(fù)雜度，平均時(shí)間復(fù)雜度，均攤時(shí)間復(fù)...