快捷導(dǎo)航

關(guān)于python類SortedList詳解

更新時(shí)間：2021年09月04日 09:43:19 作者：阿榮Jura

這篇文章主要介紹了關(guān)于python類SortedList詳解，可以幫大家鞏固一下python類的基礎(chǔ)知識(shí)，有需要的朋友可以借鑒參考下，希望可以對(duì)廣大讀者有所幫助

SortedList 有序序列

class sortedcontainers.SortedList(iterable=None, key=None)

方法

1.添加值

SortedList.add(value) 添加新元素，并排序。時(shí)間復(fù)雜度O(log(n)).
SortedList.update(iterable) 對(duì)添加的可迭代的所有元素排序。時(shí)間復(fù)雜度O(k*log(n)).

2.移除值

SortedList.clear() 移除所有元素。時(shí)間復(fù)雜度O(n).
SortedList.discard(value) 移除一個(gè)值元素，如果元素不存在，不報(bào)錯(cuò)。時(shí)間復(fù)雜度O(log(n)).
SortedList.remove(value) 移除一個(gè)值元素，如果元素不存在，報(bào)錯(cuò)ValueError。時(shí)間復(fù)雜度O(log(n)).
SortedList.pop(index=-1) 移除一個(gè)指定下標(biāo)元素，如果有序序列為空或者下標(biāo)超限，報(bào)錯(cuò)IndexError. 時(shí)間復(fù)雜度O(log(n

3.查找

SortedList.bisect_left(value) 查找元素可以插入的位置下標(biāo)，如果這個(gè)value已經(jīng)存在，則插入已經(jīng)存在的所有values之前（左側(cè)）.時(shí)間復(fù)雜度O(log(n)).

s = SortedList([1,2,3,9,8,6,5,5,5,5,5])
s.bisect_left(5)
Out[5]: 3
s
Out[6]: SortedList([1, 2, 3, 5, 5, 5, 5, 5, 6, 8, 9])

SortedList.bisect_right(value) 查找元素可以插入的位置下標(biāo)，如果這個(gè)value已經(jīng)存在，則插入已經(jīng)存在的所有values之后（右側(cè)）。時(shí)間復(fù)雜度O(log(n)).

s.bisect_right(5)
Out[7]: 8
s
Out[8]: SortedList([1, 2, 3, 5, 5, 5, 5, 5, 6, 8, 9])

SortedList.count(value) 查找元素出現(xiàn)的次數(shù)。時(shí)間復(fù)雜度O(log(n)).

s.count(5)
Out[9]: 5

SortedList.index(value, start=None, Stop=None) 查找索引范圍[start,stop）內(nèi)第一次出現(xiàn)value的索引，如果value不存在，報(bào)錯(cuò)ValueError. 時(shí)間復(fù)雜度O(log(n)).

4.迭代值

SortedList.irange(minimun=None, maximum=None, inclusive=True, True, reverse=False) 返回value=[minimun，maximum]之間的可迭代值，inclusive = Ture, True 第一個(gè)True表示包括索引minimun，第二個(gè)Ture表示包括索引maximum，reverse是表示返回的可迭代值是否反轉(zhuǎn)。
SortedList.islice(start=None, stop=None, reverse=False) 返回index=[start, stop)之間的可迭代值（切片）。

5. 其他

SortedList.copy() 返回一個(gè)淺拷貝有序序列。時(shí)間復(fù)雜度O(n)。

淺拷貝（1）直接賦值，默認(rèn)淺拷貝傳遞對(duì)象的引用而已，原始列表改變，被賦值的列表也會(huì)做相同的改變。

a = [1,2,3]
b=a
b
Out[60]: [1, 2, 3]
a[0]=0
a
Out[62]: [0, 2, 3]
b
Out[63]: [0, 2, 3]

淺拷貝(2)copy函數(shù)，淺拷貝傳遞子對(duì)象的引用，原始數(shù)據(jù)改變，只有子對(duì)象會(huì)改變。

a = [[1],2,3]
b = a.copy()
a
Out[85]: [[1], 2, 3]
b
Out[86]: [[1], 2, 3]
# 對(duì)象不改變
a.append(4)
a
Out[88]: [[1], 2, 3, 4]
b
Out[89]: [[1], 2, 3]
# 子對(duì)象跟著改變
a[0].append(2)
a
Out[91]: [[1, 2], 2, 3, 4]
b
Out[92]: [[1, 2], 2, 3]

在這里插入圖片描述