V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
oneTimeElastic
V2EX  ›  算法

找出列表中的元素对升序排列

  •  
  •   oneTimeElastic · 2020-09-09 12:00:57 +08:00 · 1275 次点击
    这是一个创建于 1525 天前的主题,其中的信息可能已经有所发展或是发生改变。

    如果有输入 a₁, ..., aₙ, n 为偶数且 aᵢ ∈ ℝ. 使用曼哈顿距离为距离方程,即 dis(aᵢ, aⱼ) = | aᵢ − aⱼ |. 输出应为列表中的 n/2 个元素对,以距离升序排列。

    如 input [1, 0.4, 3, 1.1], output [(1, 1.1), (0.4, 3)].

    input [1, 0.1, 2, 2.4, 3, 4, 1.5], output [(2, 2.4), (1, 1.5), (3, 4)].

    我自己想是用笨办法算出所有 C(n,2)的组合计算距离再排列。

    def not_in_pair_of_list(i, ls):
        return not i in [p[0] for p in ls] + [p[1] for p in ls]
    
    def calc(ls):
        ls = sorted(ls)
        d ={}
        for idx1, i in enumerate(ls[:-1]):
            for idx2, j in enumerate(ls[idx1+1:], idx1 + 1):
                d[(i,j)] = j - i
                
        res = []
        for pair in sorted(d, key = lambda k: d[k]):
            i, j = pair
            if not_in_pair_of_list(i, res) and not_in_pair_of_list(j, res):
                res.append(pair)
        return res
    
    ls = [1, 0.1, 2, 2.4, 3, 4, 1.5]
    assert calc(ls) == [(2, 2.4), (1, 1.5), (3, 4)]
    

    可这只有 O(n²)。有没有大神支招,看看有没有更快的。我觉得用 minheap 可以,但提取出新元素对时还要重新计算。

    5 条回复    2020-09-09 14:12:00 +08:00
    EPr2hh6LADQWqRVH
        1
    EPr2hh6LADQWqRVH  
       2020-09-09 12:14:39 +08:00
    什么乱七八糟的
    oneTimeElastic
        2
    oneTimeElastic  
    OP
       2020-09-09 12:32:09 +08:00
    @avastms 就是对所有的元素的配对,以各元素对的距离排序。但各元素在返回值里只能出现一次。
    EPr2hh6LADQWqRVH
        3
    EPr2hh6LADQWqRVH  
       2020-09-09 13:39:59 +08:00 via Android
    sort reverse zip slice
    JeffGe
        4
    JeffGe  
       2020-09-09 14:02:33 +08:00 via Android
    你的代码碰到重复元素就错了
    binux
        5
    binux  
       2020-09-09 14:12:00 +08:00 via Android
    我觉得你看错题了,不然太简单了。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3727 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 19ms · UTC 00:51 · PVG 08:51 · LAX 16:51 · JFK 19:51
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.