posts - 403, comments - 310, trackbacks - 0, articles - 7
            BlogJava :: 首頁 :: 新隨筆 :: 聯系 :: 聚合  :: 管理

          Nuts-and-Bolts Problem

          Posted on 2007-07-25 16:01 ZelluX 閱讀(398) 評論(0)  編輯  收藏 所屬分類: Algorithm

          問題:

          有n個大小各不相同的螺帽及對應的螺釘,要求在O(nlogn)的復雜度內完成配對。螺釘之間、螺帽之間都無法直接比較大小,只能比較一顆螺帽與螺釘,判斷他們之間的大小差異。

          感覺和快速排序的partition差不多。

          首先任選一顆螺釘與各螺帽進行比較,分成大小兩組,另外得到與改螺釘相匹配的螺帽。

          然后用那個螺帽再和其他螺釘比較,也分成大小兩組,然后繼續二分遞歸。

           

           

          主站蜘蛛池模板: 灵川县| 宁陕县| 江口县| 清涧县| 安康市| 青河县| 边坝县| 台江县| 阿尔山市| 海阳市| 潜山县| 克拉玛依市| 新竹县| 长春市| 桐柏县| 体育| 如皋市| 林州市| 会理县| 渭南市| 波密县| 湘潭县| 始兴县| 阳新县| 玉田县| 河曲县| 东宁县| 游戏| 昭苏县| 涪陵区| 天台县| 永年县| 海兴县| 昌吉市| 资溪县| 城步| 宜春市| 福泉市| 北票市| 徐闻县| 璧山县|