1

## 發現一個python好用函式庫，能夠維護排序的陣列- Leetcode 1649. Create Sorted Array through Instructions

1649. Create Sorted Array through Instructions

(其實就是insertion sort)

(由於答案可能很大，答案請回傳10^9+7)

Input: instructions = [1,2,3,6,5,4]
Output: 3
Explanation: Begin with nums = [].
Insert 1 with cost min(0, 0) = 0, now nums = [1].
Insert 2 with cost min(1, 0) = 0, now nums = [1,2].
Insert 3 with cost min(2, 0) = 0, now nums = [1,2,3].
Insert 6 with cost min(3, 0) = 0, now nums = [1,2,3,6].
Insert 5 with cost min(3, 1) = 1, now nums = [1,2,3,5,6].
Insert 4 with cost min(3, 2) = 2, now nums = [1,2,3,4,5,6].
The total cost is 0 + 0 + 0 + 0 + 1 + 2 = 3.

• 1 <= instructions.length <= 10^5

insertion sort的時間複雜度又是O(n^2)，

# each search O(log n), insert O(n)- 超時

from bisect import bisect_left, bisect_right
class Solution:
def createSortedArray(self, instructions: List[int]) -> int:
arr = []
cost = 0
for e in instructions:
left = bisect_left(arr, e)
right = len(arr)-bisect_right(arr, e)
cost += min(left, right)
arr.insert(left,e)
return cost%(10**9+7)

# SortedList簡介

SortedList來自函式庫sortedcontainers，

# 函式庫SortedList，each search&insert O(log n)

from sortedcontainers import SortedList
class Solution:
def createSortedArray(self, instructions: List[int]) -> int:
arr = SortedList()
cost = 0
for e in instructions:
left = arr.bisect_left(e)
right = len(arr)-arr.bisect_right(e)
cost += min(left, right)