Python

Question

我在 Python 中找不到以下功能：

Given a set of numbers, return the largest number less than or equal to n or return None if no such number exists.

例如，给定列表 [1, 3, 7, 10] 和 n = 9，该函数将 return 7.

我正在寻找类似于 Java's TreeSet.lower 的 Python 功能。

我可以使用另一种数据结构。堆似乎合适。

O(n) 解决方案对于问题的规模来说太慢了。我正在寻找 O(log n) 解决方案。

背景

我正在研究 https://www.hackerrank.com/challenges/maximise-sum。可能的值范围为 1 - 10^14，因此使用带有二进制搜索的排序列表太慢了。

我目前的想法是直接迭代Python's heapq backing array。我希望能有更多的东西 Pythonic.

Answer 1

如果你不能对数组的排序做出任何假设，那么我认为你能做的最好的是 O(n):

def largest_less_than(numlist, n):
    answer = min(numlist, key=lambda x: n-x if n>=x else float('inf'))
    if answer > n:
        answer = None
    return answer

如果问题是关于在同一数据集上重复获取不同 n 值的最大值，那么也许一种解决方案是重复使用 bucket sort to get your list sorted in O(n), and then use bisect。

Answer 2

nextLowest  = lambda seq,x: min([(x-i,i) for i in seq if x>=i] or [(0,None)])

用法：

t = [10, 20, 50, 200, 100, 300, 250, 150]
print nextLowest(t,55)
> 50

我从 similar question.

中获取上述解决方案

Answer 3

您可以为此使用 selection algorithm。下面我为此提供了一个简单的算法：

numbers = [1, 3, 7, 10]
n = 9
largest_number = None
for number in numbers:    
    if number<=n:
        largest_number=number
    else:
        break

if largest_number:
    print 'value found ' + str(largest_number)
else:
    print 'value not found'

Answer 4

我认为你可以为此使用 bintrees 库：https://bitbucket.org/mozman/bintrees/src

示例：

tree = bintrees.RBTree()
In [10]: tree.insert(5,1) 
In [11]: tree.insert(6,1) 
In [12]: tree.insert(10,1)
tree.ceiling_item(5)  -> (5,1)

这个操作的复杂度是O(logN)

Answer 5

如果你不必支持列表的动态添加和删除，那么只需对其进行排序并使用二进制搜索在 O(log N) 时间内找到最大的 < n。

Answer 6

ig-melnyk 的回答可能是完成这道题的正确方法。但是由于 HackerRank 没有使用库的方法，这里是我用于解决问题的 Left-Leaning Red Black Tree 的实现。

class LLRB(object):

    class Node(object):
        RED = True
        BLACK = False

        __slots__ = ['value', 'left', 'right', 'color']

        def __init__(self, value):
            self.value = value
            self.left = None
            self.right = None
            self.color = LLRB.Node.RED


        def flip_colors(self):
            self.color = not self.color
            self.left.color = not self.left.color
            self.right.color = not self.right.color


    def __init__(self):
        self.root = None


    def search_higher(self, value):
        """Return the smallest item greater than or equal to value.  If no such value
        can be found, return 0.

        """
        x = self.root
        best = None
        while x is not None:
            if x.value == value:
                return value
            elif x.value < value:
                x = x.left
            else:
                best = x.value if best is None else min(best, x.value)
                x = x.right

        return 0 if best is None else best

    @staticmethod
    def is_red(node):
        if node is None:
            return False
        else:
            return node.color == LLRB.Node.RED


    def insert(self, value):
        self.root = LLRB.insert_at(self.root, value)
        self.root.color = LLRB.Node.BLACK


    @staticmethod
    def insert_at(node, value):
        if node is None:
            return LLRB.Node(value)

        if LLRB.is_red(node.left) and LLRB.is_red(node.right):
            node.flip_colors()

        if node.value == value:
            node.value = value
        elif node.value < value:
            node.left = LLRB.insert_at(node.left, value)
        else:
            node.right = LLRB.insert_at(node.right, value)


        if LLRB.is_red(node.right) and not LLRB.is_red(node.left):
            node = LLRB.rotate_left(node)
        if LLRB.is_red(node.left) and LLRB.is_red(node.left.left):
            node = LLRB.rotate_right(node)

        return node

Answer 7

您可以减少要查找的数量，直到找到为止。

此函数将找到最大数 <= n 在 fs 中的位置，fs 是一个排序的整数列表。

如果没有小于或等于n的数字，它将return -1。

def findmaxpos(n):
  if n < fs[0]: return -1  
  while True:
    if n in fs: return fs.index(n)
    n-=1

Python - 获取堆中小于 n 的最大数

Python - Get largest number in heap that is less than n

algorithm

heap

dynamic-programming

背景