二分查找
这道题刷新了我的三观, 以前以为二分搜索只能用在单调序列或者单调函数上, 现在发现单调性并不是使用二分查找的必要条件.
二分搜索使用的必要条件: 有办法确定答案在哪半边, 左边还是右边?
使用的算法与教材里面的一样.
代码具体实现的时候, 稍微让我卡顿的地方:
1. 一开始没看懂输入是什么意思, 后来研究了一下, 发现是图的邻接矩阵.
2. 当达到二分查找的结束条件”l == r”的时候, 好像还是无法确定插入的位置, 研究了一下, 发现再添加一个比较操作, 即可, 就可以确定插入在l的左边还是右边了.
时间复杂度
用二分法查找插入的位置, 每次O(log(N)), 总共进行了N次: O(N*log(N))
对list进行插入, 每次O(N), 总共进行了N次: O(N^2)
因此, 总体的时间复杂度是O(N^2)
Python 代码
# Forward declaration of compare API.
# def compare(a, b):
# @param a, b int
# @return bool
# return bool means whether a is less than b.
class Solution(object):
def specialSort(self, N):
"""
:type N: int
:rtype: List[int]
"""
ans = [1]
for k in range(2, N + 1):
l, r = 0, k - 2
while l < r:
mid = (l + r) >> 1
if compare(k, ans[mid]):
r = mid
else:
l = mid + 1
if compare(k, ans[l]):
ans.insert(l, k)
else:
ans.insert(l + 1, k)
return ans