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

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

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

使用鏈表結(jié)構(gòu)可以克服數(shù)組鏈表需要提前知道數(shù)據(jù)大小的缺點(diǎn)。鏈表結(jié)構(gòu)可以充分利用計(jì)算機(jī)內(nèi)存空間，實(shí)現(xiàn)靈活的動(dòng)態(tài)內(nèi)存管理。然而，鏈表失去了隨機(jī)數(shù)組讀取的優(yōu)勢(shì)，由于增加了節(jié)點(diǎn)的指針字段，鏈表的空間開(kāi)銷相對(duì)較大。鏈表最明顯的優(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ī)訪問(wèn)。鏈表有許多不同的類型：?jiǎn)蜗蜴湵?、雙向鏈表和循環(huán)鏈表。鏈表可以用許多編程語(yǔ)言實(shí)現(xiàn)。鏈表的訪問(wèn)和操作包含在LISP和scheme等語(yǔ)言的內(nèi)置數(shù)據(jù)類型中。編程語(yǔ)言或面向?qū)ο笳Z(yǔ)言（如C、C和Java）依賴于變量工具來(lái)生成鏈表。

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

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