LeetCode算法题整理（线段树篇）SegmentTree

Posted on   |   Updated on | In | | Visitors

1649. Create Sorted Array through Instructions

根据指令数组创建一个有序的数组。每次新增数时的花费为，min(小于此数的个数，大于此数的个数)。

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

方法一：凭借此题达成了AK，卡着超时线过的，用了8s多。以为过不了呢，因为分析出来时间复杂度为O(n^2)。

1
2
3
4
5
6
7
8
9
def createSortedArray(self, instructions: List[int]) -> int:
    ans, mod =0, 10**9 + 7
    nums = []
    for d in instructions:
        left = bisect.bisect_left(nums, d)
        right = bisect.bisect(nums, d)
        ans += min(left, len(nums)-right)
        bisect.insort(nums, d)
    return ans % mod

方法二：使用SortedList，这个添加一个值的时间复杂度为O(logn)而不像bisect.insort是O(n)。5s多。

1
2
3
4
5
6
7
8
9
def createSortedArray(self, instructions: List[int]) -> int:
    from sortedcontainers import SortedList
    ans, mod =0, 10**9 + 7
    nums = SortedList()
    for d in instructions:
        cost = min(nums.bisect_left(d), len(nums)-nums.bisect_right(d))
        ans = (ans+cost) % mod
        nums.add(d)
    return ans