※ 引述《DJWS (...)》之铭言： : 依序扫描n个中位数 O(n) : 比x小(大)的中位数 : 其所对应的阵列，预计删除小(大)的那一半 : 也就是 low = (low + high) / 2 + 1; O(1) : (或者 high = (low + high) / 2 - 1;) : 预计更新阵列大小为 size = high - low + 1 O(1) : 累计欲删除的元素数量 y (小的那些) O(1) : 如果第k个元素小於等於 y，那麽就删除最大的那 1/4，下个回合找第 k 小的元素 : 否则就删除最小的那 1/4，下个回合找第 k = Σsize - y 大的元素 对於这里我有点困惑 若k<=y，删除叫大的那些数是没问题的，因为那些数一定比第k个数还大 但是当k>y时，真的能删除较小的那一部分嘛? 例如说现在有7*7的矩阵 1, 2, 3, 4, 5, 6, 7 8, 9,10,11,12,13,14 15,16,17,18,19,20,21 22,23,24,25,26,27,28 29,30,31,32,33,34,35 36,37,38,39,40,41,42 43,44,45,46,47,48,49 并且我要找的数是第17小的数 但比较小的那部分却只有16个数 於是按照这个演算法我们就会把真正的第17小的数给移除了0.0(我没理解错的话...) --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 140.112.28.238 ※ 文章网址: http://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1413348969.A.3EC.html