問(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}。
您可能感興趣的試卷
你可能感興趣的試題

最新試題
馬的遍歷問(wèn)題能否有可行解,與()有關(guān)。
題型:多項(xiàng)選擇題
有一個(gè)問(wèn)題的蒙特卡洛算法,給定一個(gè)實(shí)例,已知運(yùn)行一次其答案是錯(cuò)誤的概率是1/8,現(xiàn)運(yùn)行k次該算法,其答案一直不變,問(wèn)該答案的正確率是()。
題型:?jiǎn)雾?xiàng)選擇題
在求解部分背包問(wèn)題時(shí)采用的貪心策略是()。
題型:?jiǎn)雾?xiàng)選擇題
關(guān)于使用回溯法求解0-1背包問(wèn)題,以下說(shuō)法正確的是()。
題型:多項(xiàng)選擇題
將長(zhǎng)度分別為m,n的兩個(gè)單鏈表合并為一個(gè)單鏈表的時(shí)間復(fù)雜度為O(m+n)。
題型:判斷題