問(wèn)答題求解最接近中位數(shù)的k個(gè)數(shù):給定由n個(gè)互不相同的數(shù)組成的集合A以及正整數(shù)k≤n,設(shè)計(jì)一個(gè)O(n)時(shí)間復(fù)雜度的查找A中最接近A的中位數(shù)的k個(gè)數(shù)的算法。在采用分治法進(jìn)行查找時(shí),為了滿(mǎn)足分治法的平衡原則,需要將數(shù)組分成兩個(gè)大小基本相同的子數(shù)組,其中的那個(gè)劃分點(diǎn)就是中位數(shù)。所以,中位數(shù)是指數(shù)組中能將數(shù)組劃分成兩個(gè)大小基本相同的兩個(gè)子數(shù)組的那個(gè)元素,即中位數(shù)是第「n/2」小的數(shù)。根據(jù)b找出所要的解{|a-mid|≤b,a∈A}。

您可能感興趣的試卷