扫描二维码,下载安卓APP
下载安卓APP箭头
客服QQ
箭头给我发消息

客服QQ:2698585038
论坛 >编程语言 >Swift 算法实战之路:排序(排序实战)

Swift 算法实战之路:排序(排序实战)

课课家iOS游客发布于 2017-09-14 09:14查看:9055回复:1

     排序实战

        直接来看一道Facebook, Google, Linkedin都考过的面试题。

        已知有很多会议,如果有这些会议时间有重叠,则将它们合并。
        比如有一个会议的时间为3点到5点,另一个会议时间为4点到6点,那么合并之后的会议时间为3点到6点

        解决算法题目第一步永远是把具体问题抽象化。这里每一个会议我们已知开始时间和结束时间,就可以写一个类来定义它:

image.png

        然后题目说已知有很多会议,就是说我们已知有一个MeetingTime的数组、所以题目就转化为写一个函数,输入为一个MeetingTime的数组,输出为一个将原数组中所有重叠时间都处理过的新数组。

image.png

        下面来分析一下题目怎么解。最基本的思路是遍历一次数组,然后归并所有重叠时间。举个例子:[[1, 3], [5, 6], [4, 7], [2, 3]]。这里我们可以发现[1, 3]和[2, 3]可以归并为[1, 3],[5, 6]和[4, 7]可以归并为[5, 7]。所以这里就提出一个要求:要将所有可能重叠的时间尽量放在一起,这样遍历的时候可以就可以从前往后一个接着一个的归并。于是很自然的想到 — 按照会议开始的时间排序。

        这里我们要对一个class进行排序,而且要自定义排序方法,在Swift中可以这样写:

image.png

        意思就是首先对开始时间进行升序排列,如果它们相同,就比较结束时间。

        有了排好顺序的数组,要得到新的归并后的结果数组,我们只需要在遍历的时候,每次比较原数组(排序后)当前会议时间与结果数组中当前的会议时间,假如它们有重叠,则归并;如果没有,则直接添加进结果数组之中。所有代码如下:

image.png

     展望

        排序在Swift中的应用场景很多,比如tableView中对于dataSource的处理。当然很多时候,排序都是和搜索,尤其是二分搜索配合使用。下期探讨搜索的时候,会对排序进行进一步拓展。



收藏(0)0
查看评分情况

全部评分

此主贴暂时没有点赞评分

总计:0

回复分享

版主推荐

    共有1条评论

    • 课课家运营团队
    • Mr ken
    • YUI
    • cappuccino
    • mr jack
    • IT宅男
    • Mright
    • 选择版块:

    • 标题:

    • 内容

    • 验证码:

    • 标题:

    • 内容

    • 选择版块:

    移动帖子x

    移动到: