假设给出了一个未排序的正整数列表,并且您希望以这样的方式对它们进行排序:元素交替为:(小于前一个元素),(大于前一个元素),(小于前一个元素)等. ..输出列表中的第一个元素可能会忽略该规则.例如,假设您的列表是:1,4,9,2,7,5,3,8,6.
一个正确的输出将是...... 1,9,2,8,3,7,4,6,5
另一个是...... 3,4,2,7,5,6,1,9,8
假设列表不包含重复项,任意大,并且尚未排序.
现在,标准方法是首先按升序对列表进行排序,然后交替从列表末尾剥离元素.但是,我想知道:如果没有先对列表进行排序,是否有更省时的方法？
我的理由是:(只在你关心的情况下阅读此内容)
显然这是我姐姐的男朋友在旧金山的求职面试中给人们提出的一个问题.我妹妹问了我这个问题,我立刻想出了标准回答.这就是每个人都回答的问题.然而,显然有一个女孩提出了一个完全不同的解决方案,不需要对列表进行排序,它似乎工作.我妹妹无法向我解释这个解决方案,但自从昨晚以来,这个想法让我感到困惑.我很感激任何帮助!谢谢!