AcWing 113. 特殊排序
原题链接
简单
作者:
皓首不倦
,
2020-09-15 22:09:02
,
所有人可见
,
阅读 353
from functools import lru_cache
@lru_cache(typed=False, maxsize=128000000)
def cmp(a, b):
return compare(a, b)
class Solution(object):
def specialSort(self, N):
arr = [1]
for cur_val in range(2, N+1):
l, r = 0, len(arr)-1
while l <= r:
mid = l + (r-l) // 2
if cmp(cur_val, arr[mid]):
# 当前值小于中间位置的值,在左边区间一定能找到插入的位置
r = mid - 1
else:
# 当前值大于中间位置的值,在右边区间一定能找到插入位置
l = mid + 1
if l - 1 == -1 or cmp(arr[l - 1], cur_val):
arr = arr[:l] + [cur_val] + arr[l:]
elif r - 1 == -1 or cmp(arr[r - 1], cur_val):
arr = arr[:r] + [cur_val] + arr[r:]
return arr