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差不多。

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

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

           

           

          主站蜘蛛池模板: 讷河市| 盐池县| 平罗县| 什邡市| 尉犁县| 尖扎县| 柘荣县| 福海县| 光泽县| 蓝田县| 桦川县| 新蔡县| 从江县| 东丽区| 东丰县| 南川市| 莱西市| 台山市| 闽清县| 泰来县| 招远市| 隆回县| 德安县| 泗洪县| 邓州市| 沈阳市| 青河县| 潜江市| 泌阳县| 西乌| 天全县| 集安市| 黔江区| 铁力市| 隆昌县| 苏州市| 华宁县| 海门市| 平阴县| 清水县| 五河县|