我正在创建一个类,其中一个方法将新项插入到排序列表中。该项目将插入已排序列表中的已更正(已排序)位置。我不允许使用除[]
,[:]
,+
和len
之外的任何内置列表函数或方法。这是让我感到困惑的部分。
解决这个问题的最佳方法是什么?
提示1:您可能想要在bisect module中学习Python代码。
提示2:Slicing可用于列表插入:
>>> s = ['a', 'b', 'd', 'e']
>>> s[2:2] = ['c']
>>> s
['a', 'b', 'c', 'd', 'e']
您应该使用bisect模块。此外,在使用bisect.insort_left之前,需要对列表进行排序
这是一个非常大的差异。
>>> l = [0, 2, 4, 5, 9]
>>> bisect.insort_left(l,8)
>>> l
[0, 2, 4, 5, 8, 9]
timeit.timeit("l.append(8); l = sorted(l)",setup="l = [4,2,0,9,5]; import bisect; l = sorted(l)",number=10000)
1.2235019207000732
timeit.timeit("bisect.insort_left(l,8)",setup="l = [4,2,0,9,5]; import bisect; l=sorted(l)",number=10000)
0.041441917419433594
这是一个可能的解决方案:
a = [15, 12, 10]
b = sorted(a)
print b # --> b = [10, 12, 15]
c = 13
for i in range(len(b)):
if b[i] > c:
break
d = b[:i] + [c] + b[i:]
print d # --> d = [10, 12, 13, 15]
我现在正在学习算法,所以我想知道bisect模块是如何写的。以下是bisect模块中关于将项目插入到排序列表中的代码,该列表使用二分法:
def insort_right(a, x, lo=0, hi=None):
"""Insert item x in list a, and keep it sorted assuming a is sorted.
If x is already in a, insert it to the right of the rightmost x.
Optional args lo (default 0) and hi (default len(a)) bound the
slice of a to be searched.
"""
if lo < 0:
raise ValueError('lo must be non-negative')
if hi is None:
hi = len(a)
while lo < hi:
mid = (lo+hi)//2
if x < a[mid]:
hi = mid
else:
lo = mid+1
a.insert(lo, x)
这是附加列表并将值插入排序列表的最佳方法:
a = [] num = int(input('How many numbers: ')) for n in range(num):
numbers = int(input('Enter values:'))
a.append(numbers)
b = sorted(a) print(b) c = int(input("enter value:")) for i in
range(len(b)):
if b[i] > c:
index = i
break d = b[:i] + [c] + b[i:] print(d)`