一道java面試題，20億數(shù)字的文本排序，如何取前100？因?yàn)檫@是一個Java問題，所以這是典型的TOPK問題。首先取前100個數(shù)字構(gòu)建一個最小堆，然后依次從堆的頂部插入剩余的數(shù)字，同時調(diào)整堆。堆中最

一道java面試題，20億數(shù)字的文本排序，如何取前100？

因?yàn)檫@是一個Java問題，所以這是典型的TOPK問題。首先取前100個數(shù)字構(gòu)建一個最小堆，然后依次從堆的頂部插入剩余的數(shù)字，同時調(diào)整堆。堆中最后100個元素就是結(jié)果。鏈表是物理存儲單元上的一種非連續(xù)、非順序的存儲結(jié)構(gòu)。數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接順序來實(shí)現(xiàn)的。鏈表由一系列節(jié)點(diǎn)組成（鏈表中的每個元素稱為節(jié)點(diǎn)），這些節(jié)點(diǎn)可以在運(yùn)行時動態(tài)生成。每個節(jié)點(diǎn)包括兩部分：一部分是存儲數(shù)據(jù)元素的數(shù)據(jù)字段，另一部分是存儲下一個節(jié)點(diǎn)地址的指針字段。與線性表序結(jié)構(gòu)相比，操作更為復(fù)雜。由于鏈表不需要按順序存儲，因此鏈表插入時的復(fù)雜度可以達(dá)到o（1），比其他線性序列表快得多。但是，查找節(jié)點(diǎn)或訪問具有特定編號的節(jié)點(diǎn)需要O（n）個時間。線性表和序列表的時間復(fù)雜度分別為o（logn）和o（1）。

使用鏈表結(jié)構(gòu)可以克服數(shù)組鏈表需要提前知道數(shù)據(jù)大小的缺點(diǎn)。鏈表結(jié)構(gòu)可以充分利用計(jì)算機(jī)內(nèi)存空間，實(shí)現(xiàn)靈活的動態(tài)內(nèi)存管理。然而，鏈表失去了隨機(jī)數(shù)組讀取的優(yōu)勢，由于增加了節(jié)點(diǎn)的指針字段，鏈表的空間開銷相對較大。鏈表最明顯的優(yōu)點(diǎn)是關(guān)聯(lián)項(xiàng)的常規(guī)數(shù)組排列可能與這些數(shù)據(jù)項(xiàng)在內(nèi)存或磁盤中的排列順序不同，數(shù)據(jù)的存取往往需要按不同的排列順序進(jìn)行轉(zhuǎn)換。鏈表允許在列表的任何位置插入和刪除節(jié)點(diǎn)，但不允許隨機(jī)訪問。鏈表有許多不同的類型：單向鏈表、雙向鏈表和循環(huán)鏈表。鏈表可以用許多編程語言實(shí)現(xiàn)。鏈表的訪問和操作包含在LISP和scheme等語言的內(nèi)置數(shù)據(jù)類型中。編程語言或面向?qū)ο笳Z言（如C、C和Java）依賴于變量工具來生成鏈表。

鏈表是誰發(fā)明的？

我猜您向人們詢問了各種JDK數(shù)據(jù)結(jié)構(gòu)的基本實(shí)現(xiàn)原則。事實(shí)上，我一直在想。知道基本的實(shí)現(xiàn)原則是可以的，也是值得的，但是如果你不知道呢？人們知道哪些數(shù)據(jù)結(jié)構(gòu)適用于哪些場景，并且能夠熟練地使用它們。那不是。。。夠了嗎？對貴公司的需求不足嗎？你希望他為你的公司創(chuàng)建一個新的數(shù)據(jù)結(jié)構(gòu)嗎？就像two peas或JDK一樣，JDK的數(shù)據(jù)結(jié)構(gòu)性能遇到了瓶頸，求職者會給你提供比工作提供的數(shù)據(jù)結(jié)構(gòu)更好的數(shù)據(jù)結(jié)構(gòu)。