LeetCode算法题-29. 两数相除（Swift）

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。

返回被除数 dividend 除以除数 divisor 得到的商。

示例 1:

示例 2:

说明:

之前 的方法都超时了，这个方法也只击败了70%的用户。但是我实在想不起来，不使用乘法、除法和 mod 运算符还能怎么优化。先这样吧。

在 Swift 的日常开发中，或多或少会遇到数组排序

笔者最近遇到了一个排序的问题

群里提问之后

一个小总结

你别嫌我菜， 不菜没人爱

 

一般的排序 比如：

根据 Person 的 age 进行 升序/降序，一般我们通过 Swift 内置排序 sorted 去解决

sorted 会产生新的结果，不影响原有的序列； 而 sort() 会将结果保存在原有的数组中

 

我不知道你没有思考过这样一个问题

就是

sort 排序的原理是什么？

 

 

Swift 的内置排序算法 sort() 在 Swift5 之后采用了 TimSort ，相较于之前的 Introsort 更 stability

什么是 stability ？

一种排序后维持相等元素的原始顺序的能力

比如

在真实数据下可能会影响到 排序的先后稳定性

音乐 app 按照 热门度 去排列 hit song

如果不够 stability ，那么 相同 热门度的歌曲，可能每次的排序结果就会有差别

 

而 TimSort 也是一种混合算法 ， 插入排序O(n^2) + 归并排序O(nlogn) ， 因为 插入 和 归并都是 stability ， 所以 TimSort 也是

TimSort 核心原理是 切割 + 合并

具体实现可参考 TimSort

所以以此看来， sort 算法的时间复杂度是 O(nlogn)

 

笔者的需求是:

有一个 origin list 但信息不全， 要通过 origin list 的 id 数组 去请求具体的 detail list

覆盖 origin list

但是返回的 detail list 并没有按照 ids 的请求顺序 排序 （不是升序 / 降序）

需要手动排序

 

题目可以理解为 ：

 

 

暴力解法 : 双层 for循环, 时间复杂度 O(n^2)

高阶函数 ：flatMap + filter， 类似暴解，时间复杂度 O(n^2)

由 @SAGES** 提出 ：

flatMap :

将结果合并为一个新的数组，自动去 nil，同时会把 Optional 的值解包

由于嵌套关系，省略常数，故本解 时间复杂度也为 O(n^2)

 

先将模型数组 映射到字典， 再 对 ids map 去字典内查找，时间复杂度 O(n)

由 @Damonwo** 提出

总体为 O(2n) =>故 此解法 O(n)

 

笔者开始想用 sort ， 奈何对 sort 的理解 如登月一般

停留在表面， so

此解

由 @冬* 提出

此解第一步 将 ids 数组，按照 下标 映射到 字典内

得到

[23: 1, 77: 2, 56: 3, 9: 0, 87: 4]

最后通过 sorted 闭包 对 person 的 age 进行 index 权重 升序排序

 

最终得到

[77: 2, 9: 0, 87: 5, 56: 4, 23: 1]

 

所以总的时间为 O(n) + O(n) + O(nlogn) ,取较大的值 即： O(nlogn)

 

此解 同 sort1 的 解法思路大致相同， 时间复杂度 为 O(nlogn)

由 @提拉米不**、提出

优化之后也是将 firstIndex 这一步 放入 map，降低查找时间复杂度

即

思路等同于 sort1

所以总的时间为 O(n) + O(nlogn) ,取较大的值 即： O(nlogn)

 

实际开发中

算法的选择还是很秒的

不考虑 时间复杂度，高阶函数会让 Swift 变的优雅；反之尽量采用 较低的 时间复杂度

尽管是一次小小的条件排序

 

选择越多

才会分优劣

 

欢迎分享自己的方法 ～

---