不知名代码星球
文章 标签 分类
不知名代码星球

目录

三个月算法进阶--day77

   约 508 字   预计阅读 2 分钟    次阅读  

有序序列的查找与插入，bisect.bisect/bisect.bisect_left/bisect.insort/bisect.insort_left

当序列的值域很大，算法复杂度又是O(n)的，同时只用关心元素的相对大小，不关心绝对大小

动态维护序列前缀和的数据结构，单点更新和前缀和查询的时间代价为O(log n)

class BIT:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)

    @staticmethod
    def lowbit(x):
        return x & (-x)
    
    def query(self, x):
        ret = 0
        while x > 0:
            ret += self.tree[x]
            x -= BIT.lowbit(x)
        return ret

    def update(self, x):
        while x <= self.n:
            self.tree[x] += 1
            x += BIT.lowbit(x)


class FenwickTree:
    def __init__(self, n):
        self.size = n
        self.tree = [0 for _ in range(n + 1)]
    def __lowbit(self, index):
        return index & (-index)
    # 单点更新：从下到上，最多到 len，可以取等
    def update(self, index, delta):
        while index <= self.size:
            self.tree[index] += delta
            index += self.__lowbit(index)
    # 区间查询：从上到下，最少到 1，可以取等
    def query(self, index):
        res = 0
        while index > 0:
            res += self.tree[index]
            index -= self.__lowbit(index)
        return res

leetcode剑指offer第51题数组中的逆序对

归并排序

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        def mergeSort(nums, tmp, l, r):
            if l >= r:
                return 0
            mid = (l + r) >> 1
            count = mergeSort(nums, tmp, l, mid) + mergeSort(nums, tmp, mid + 1, r)
            i, j = l, mid + 1
            pos = l 
            while i <= mid and j <= r:
                if nums[i] <= nums[j]:
                    tmp[pos] = nums[i]
                    i += 1
                    count += (j - (mid + 1))
                else:
                    tmp[pos] = nums[j]
                    j += 1
                pos += 1
            for k in range(i, mid + 1):
                tmp[pos] = nums[k]
                count += (j - (mid + 1))
                pos += 1
            for k in range(j, r + 1):
                tmp[pos] = nums[k]
                pos += 1
            nums[l:r+1] = tmp[l:r+1]
            return count
        
        n = len(nums)
        tmp = [0] * n 
        return mergeSort(nums, tmp, 0, n-1)
更新于 2020-11-08
返回 | 主页