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

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

因?yàn)檫@是一個(gè)Java問題，所以這是典型的TOPK問題。首先取前100個(gè)數(shù)字構(gòu)建一個(gè)最小堆，然后依次從堆的頂部插入剩余的數(shù)字，同時(shí)調(diào)整堆。堆中最后100個(gè)元素就是結(jié)果?？臻g復(fù)雜度是k，時(shí)間復(fù)雜度是nlogk

看到這個(gè)問題，你可以開始聯(lián)系編程。在實(shí)際應(yīng)用中，數(shù)據(jù)庫(kù)是數(shù)據(jù)存儲(chǔ)的模塊，可以直接用于簡(jiǎn)單的服務(wù)。然而，在真正大規(guī)模、高并發(fā)的服務(wù)中，數(shù)據(jù)庫(kù)往往不被使用，即使被使用，也不會(huì)被用于排序。例如，推薦系統(tǒng)可能是一個(gè)百萬維的特征操作，涉及在線和離線等，此時(shí)，排序算法起著重要的作用。很多人默認(rèn)使用快速排序，數(shù)據(jù)量大時(shí)效率不高。實(shí)際上，最好將其轉(zhuǎn)換為桶排序

排序視情況而定，例如1到10個(gè)無序數(shù)字，定義一個(gè)包含10個(gè)元素的臨時(shí)數(shù)組，并將相應(yīng)的值寫入相應(yīng)的元素中。這種方法只需要解一次，然后比如50個(gè)隨機(jī)數(shù)，其中最大的是100，你也可以創(chuàng)建一個(gè)下標(biāo)為100的數(shù)組，循環(huán)原數(shù)組，把對(duì)應(yīng)的值寫到對(duì)應(yīng)的元素上，只需解一次，然后刪除沒有賦值的值。我試過用8W陣列做實(shí)驗(yàn)，這種方法比冒泡快得多