怎么在O(N)時(shí)間內(nèi)求一個(gè)無(wú)序數(shù)組的中位數(shù)？讓我們使用改進(jìn)的快速排序方法。每次我們看定標(biāo)的選中數(shù)是在左半部分還是在右半部分，然后根據(jù)要求對(duì)其余的進(jìn)行排序。例如，總共有10個(gè)數(shù)字。如果校準(zhǔn)的第一個(gè)數(shù)字在

怎么在O(N)時(shí)間內(nèi)求一個(gè)無(wú)序數(shù)組的中位數(shù)？

讓我們使用改進(jìn)的快速排序方法。每次我們看定標(biāo)的選中數(shù)是在左半部分還是在右半部分，然后根據(jù)要求對(duì)其余的進(jìn)行排序。例如，總共有10個(gè)數(shù)字。如果校準(zhǔn)的第一個(gè)數(shù)字在第三位，您只需要取3右邊的數(shù)字。中間帶必須在右側(cè)。理論期望值為O（n）?；蛘?，如果使用桶排序方法，則排序復(fù)雜度為O（n），只需找到中間值即可。