我有两个包含两个数字序列的列表,例如:
A = [1.0, 2.9, 3.4, 4.2, 5.5....100.3]
B = [1.1, 1.2, 1.3, 2.5, 3.0, 3.1, 5.2]
我想根据列表B中的元素是否福尔斯在列表A的(任何)区间内来创建另一个标签列表。
C = [group_1, group_1, group_1, group_1, group_2, group_2, group_3]
即1.1、1.2、1.3、2.5都落在列表A的1.0 - 2.9的区间内,因此是group_1;3.0、3.1均落在2.9 - 3.4区间内,属第2组;和5.2福尔斯在4.2 - 5.5的区间内,因此是组_3等。
列表B中的数字落在列表A的哪个区间并不重要,关键是要以连续的方式对列表B中的所有元素进行分组/标记。
原始数据很大,因此不可能手动将标签/组分配给列表B中的元素。
5条答案
按热度按时间zf9nrax11#
因此,假设
A
已经排序,那么可以使用二进制搜索,它已经在(相当笨拙的)bisect
模块中的python标准库中提供了:这需要
O(N * logN)
时间。注意,要仔细阅读documentation,当
B
中的值等于A
中的值时,bisect_left
和bisect_right
的行为,以及不会落在任何地方的项的行为。wsxa1bj12#
你可以在
O(n)
解决方案中尝试这个方法(假设两个列表都排序了,并且一个数字必须在A
中的一个区间内):图纸:
h4cxqtbf3#
您可以在
O(len(B))
中根据以下代码进行回答:dgenwo3n4#
我认为
itertools.groupby
加上一个微小的可变“key函数”会非常适合(特别是当需求可能改变,或者您需要在其他地方使用此模式时):这个方法是O(NA + NB)。
你可以通过二进制搜索
__call__
中的正确索引来消除这些先决条件,而不是假设后面的某个索引“肯定”是正确的,但是复杂度会上升到O(NB × log NA)。wqnecbli5#
试试这个: