1

假设您有以下两个列表：

l1 = [0,30,45,55,80,90]
l2 = [35,65,70,75,100,120]

列表规则：

  1. `l1` 总是从 0 开始，而 `l2` ​​必须从大于 0 开始
  2. 列表必须按从小到大的顺序

目标：

本质上，每个数字都是打开和关闭某物的索引。目标是返回l2关闭第一个项目的项目l1

解释：

中的一个项目l2将“关闭”l1其中最接近的数字小于自身的项目。那么这两个数字都不再可用。使用作为示例给出的列表，会发生以下情况：

0 打开

30个打开

35 关闭 30

45 打开

55 打开

65 关闭 55

70 关闭 45

75 关闭 0

答案 = 75

我相信有一种方法可以做到这一点，只需遍历每个列表一次。我想出的方法需要l1在关闭的情况下进行多次迭代。所以在这个例子中，它必须迭代 4 次才能得到正确的答案。这是该功能：

def f(l1,l2):
    for x in l2:
        new_l = [i for i in l1 if i < x]
        closed = new_l[-1]
        if closed == 0:
            answer = x
            break
        else:
            l1.remove(closed)
    return answer

有什么方法可以检测什么关闭了什么，这样我就不需要重复必要的次数。在我的实际情况下，这可能需要数百次迭代，因为这个函数实际上会在一个可能持续一段时间的循环中运行

4

4 回答 4

3

您可以使用该bisect模块：

import bisect
def f(l1,l2):
    for x in l2:
        ind = bisect.bisect(l1,x)
        # if the index where the item from l2 can fit in l1 is 1,
        # then it's time to return 
        if ind - 1 == 0:           
            return x
        del l1[ind-1]   #otherwise remove the item from l1


l1 = [0,30,45,55,80,90]
l2 = [35,65,70,75,100,120]
print f(l1,l2)
#75
于 2013-07-10T19:23:44.223 回答
1

这个问题是标准括号匹配问题的变体。主要区别在于，开启者和关闭者不是单一序列的开启者和关闭者，而是编号，并且它们的顺序由它们的编号定义。我们可以懒惰地将它们合并成一个序列，然后遍历序列并保持未关闭的开启者的数量，直到我们找到第一个开启者的更接近者。这在 O(n) 中运行，其中 n 是第一个开瓶器的关闭器的索引。

def merge_iterator(openers, closers):
    """Goes through the openers and closers, merging the sequences.

    Yields (opener, 1) or (closer, -1) tuples, sorted by the values of the
    openers or closers. Each yield runs in O(1).

    """
    openers = iter(openers)
    closers = iter(closers)
    opener = next(openers)
    closer = next(closers)
    try:
        while True:
            if opener < closer:
                yield opener, 1
                opener = next(openers)
            else:
                yield closer, -1
                closer = next(closers)
    except StopIteration:
        # Ran out of openers. (We can't run out of closers first.)
        yield closer, -1
        for closer in closers:
            yield closer, -1

def find_closer(openers, closers):
    merged_sequence = merge_iterator(openers, closers)

    # open the first opener
    unclosed = 1
    next(merged_sequence)

    # open and close openers until the first opener closes
    for item, change_in_unclosed in merged_sequence:
        unclosed += change_in_unclosed
        if not unclosed:
            # We closed the first opener. Return the closer.
            return item
于 2013-07-10T20:03:17.227 回答
0

这应该是O(N). 

 def find_answer(l1, l2):
    opened = 0
    curr_l2 = 0

    for el in l1:
        if el > l2[curr_l2]:
            while curr_l2 < len(l2) and el > l2[curr_l2]:
                if opened == 1:
                    return l2[curr_l2]
                elif opened > 1:
                    # l2[curr_l2] closes an element.
                    opened -= 1
                    curr_l2 += 1
                else:
                    # Noone left to close
                    return None
        # `el` opens
        opened += 1
   # Remaining elements to close left
   return None
于 2013-07-10T20:02:58.677 回答
0

这对你有用吗

def findBiggest(L, val):
    """ Basically a modified binary search """
    if len(L) == 1:
        return L[0]
    elif L[len(L)/2] >= val:
        return biggest(L[:len(L)/2], val)
    else:
        return findBiggest(L[len(L)/2:], val)

def findOpens(opens, closes):
    for c in closes:
        opener = findBiggest(opens, c)
        opens.remove(opener)
        if opener == 0:
            print 'answer =', c
            return opener
于 2013-07-10T19:20:24.827 回答