V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐学习书目
Learn Python the Hard Way
Python Sites
PyPI - Python Package Index
http://diveintopython.org/toc/index.html
Pocoo
值得关注的项目
PyPy
Celery
Jinja2
Read the Docs
gevent
pyenv
virtualenv
Stackless Python
Beautiful Soup
结巴中文分词
Green Unicorn
Sentry
Shovel
Pyflakes
pytest
Python 编程
pep8 Checker
Styles
PEP 8
Google Python Style Guide
Code Style from The Hitchhiker's Guide
liemehoc
V2EX  ›  Python

求排序算法思路,使得 array[0]<array[1]>array[2]<array[3]...

  •  
  •   liemehoc · 2017-11-27 21:04:29 +08:00 · 3604 次点击
    这是一个创建于 2559 天前的主题,其中的信息可能已经有所发展或是发生改变。

    python,如输入[8,8,4,6,2,7],输出[4,8,6,7,2,8]

    20 条回复    2017-11-29 10:47:49 +08:00
    blueset
        1
    blueset  
       2017-11-27 21:18:55 +08:00 via Android
    排序,然后左右交替取数?

    8 8 4 6 2 7 → 2 4 6 7 8 8

    2 4 6 (7 8 8)
    - 8 8 7 (6 4 2)

    2 <= 8 >= 4 <= 8 >= 6 <= 7
    jzy
        2
    jzy  
       2017-11-27 21:19:00 +08:00 via iPhone
    从小到大排序,前面一半放奇数位,后面一半放偶数位。如果奇数位和偶数位首位相等,应该是无解了
    momocraft
        3
    momocraft  
       2017-11-27 21:20:44 +08:00
    先排成升序然后反复横跳地取: arr[3] --(向左)-- arr[2] --(向右)-- arr[4] --(向左)--
    lhx2008
        4
    lhx2008  
       2017-11-27 21:21:38 +08:00 via Android
    答案不唯一呀,还要随机分布么
    ballshapesdsd
        5
    ballshapesdsd  
       2017-11-27 21:29:00 +08:00
    leetcode 上有这道题。。一模一样的
    liemehoc
        6
    liemehoc  
    OP
       2017-11-27 21:30:56 +08:00
    @blueset
    @jzy
    @momocraft
    我第一反应也是这个,不知道有没有更优雅的解法


    @lhx2008 是的,能不能算出所有有效解
    liemehoc
        7
    liemehoc  
    OP
       2017-11-27 21:32:09 +08:00
    @ballshapesdsd 名字叫啥
    ballshapesdsd
        8
    ballshapesdsd  
       2017-11-27 21:38:01 +08:00   ❤️ 1
    @liemehoc 噗,找了半天
    https://leetcode.com/problems/wiggle-subsequence/description/
    o(n)时间复杂度的解法
    liemehoc
        9
    liemehoc  
    OP
       2017-11-27 21:48:09 +08:00
    @ballshapesdsd 学习了,解法有意思
    SlipStupig
        10
    SlipStupig  
       2017-11-27 23:03:15 +08:00
    我今天也遇到类似的问题:
    python:
    list_a = ['m', 'z', 'k', 'i']
    dict_a = {'z': 2, ‘ k ’: 3, 'm':'a', 'i': -1}

    dict_a 有什么办法能优雅的按照 list_a 中的 key 顺序排列呢?
    jmc891205
        11
    jmc891205  
       2017-11-27 23:22:34 +08:00
    @SlipStupig
    [dict_a[k] for k in list_a]这样?
    dangoron
        12
    dangoron  
       2017-11-27 23:28:18 +08:00 via Android
    shell sort 做到一半的感觉。。
    panda0
        13
    panda0  
       2017-11-28 00:28:46 +08:00 via iPhone
    @jmc891205 这样是个 list 了吧
    nondanee
        14
    nondanee  
       2017-11-28 01:53:40 +08:00 via Android
    @SlipStupig dict 就是无序的呀,用 collections.OrderedDict 哇
    LukeXuan
        15
    LukeXuan  
       2017-11-28 03:07:00 +08:00
    找到中位数(O(n)),然后比中位数小的放在偶数位,大的放在奇数位。
    vegito2002
        16
    vegito2002  
       2017-11-28 03:33:32 +08:00
    Wiggle Sort, Google 原题, LC 上面有
    SlipStupig
        17
    SlipStupig  
       2017-11-28 07:24:14 +08:00
    @jmc891205 哈哈,好像是这样,但是如果是两个 list 呢?
    dangyuluo
        18
    dangyuluo  
       2017-11-28 08:36:35 +08:00
    我觉得答案不唯一吧。
    leetao94
        19
    leetao94  
       2017-11-28 08:41:54 +08:00
    liemehoc
        20
    liemehoc  
    OP
       2017-11-29 10:47:49 +08:00
    @vegito2002
    @dangyuluo
    @leetao94
    扩展一下问题,如果要求所有满足规则的解呢
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2826 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 29ms · UTC 02:33 · PVG 10:33 · LAX 18:33 · JFK 21:33
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.