blocks|key|1014113|text|我认为您可以使用二叉树库进行以下操作：https://bitbucket.org/mozman/bintrees/src|type|unstyled|depth|inlineStyleRanges|offset|length|style|BOLD|entityRanges|data|1014114|例子：|1014115|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)|code-block|syntax|javascript|1014116|这个操作的复杂性是O(logN)|1014117|entityMap|0|LINK|mutability|MUTABLE|url|https://bitbucket.org/mozman/bintrees/src^0|8|3|J|15|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|W|8|@$9|X|A|Y|B|C]]|D|@$9|Z|A|10|1|11]]|E|$]]|$1|F|3|G|5|6|7|12|8|@]|D|@]|E|$]]|$1|H|3|I|5|J|7|13|8|@]|D|@]|E|$K|L]]|$1|M|3|N|5|6|7|14|8|@]|D|@]|E|$]]|$1|O|3|-4|5|6|7|15|8|@]|D|@]|E|$]]]|P|$Q|$5|R|S|T|E|$U|V]]]]

I think you can use bintrees library for this : <a href="https://bitbucket.org/mozman/bintrees/src" rel="nofollow">https://bitbucket.org/mozman/bintrees/src</a>

Examples : 

<pre><code>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) -&gt; (5,1)
</code></pre>

The complexity of this operation is O(logN)

blocks|key|2174324|text|nextLowest++=+lambda+seq,x:+min([(x-i,i)+for+i+in+seq+if+x>=i]+or+[(0,None)])|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|2174325|用法：|unstyled|2174326|t+=+[10,+20,+50,+200,+100,+300,+250,+150]
print+nextLowest(t,55)
>+50|2174327|我从一个相似问题中获取上面的解决方案。|offset|length|2174328|entityMap|0|LINK|mutability|MUTABLE|url|https://stackoverflow.com/a/5348215/1604312^0|0|0|0|4|4|0|0^^$0|@$1|2|3|4|5|6|7|U|8|@]|9|@]|A|$B|C]]|$1|D|3|E|5|F|7|V|8|@]|9|@]|A|$]]|$1|G|3|H|5|6|7|W|8|@]|9|@]|A|$B|C]]|$1|I|3|J|5|F|7|X|8|@]|9|@$K|Y|L|Z|1|10]]|A|$]]|$1|M|3|-4|5|F|7|11|8|@]|9|@]|A|$]]]|N|$O|$5|P|Q|R|A|$S|T]]]]

<pre><code>nextLowest = lambda seq,x: min([(x-i,i) for i in seq if x&gt;=i] or [(0,None)])
</code></pre>

Usage:

<pre><code>t = [10, 20, 50, 200, 100, 300, 250, 150]
print nextLowest(t,55)
&gt; 50
</code></pre>

I take the above solution from a <a href="https://stackoverflow.com/a/5348215/1604312">similar question</a>.

blocks|key|1619219|text|如果你不能对数组的排序做任何假设，那么我认为你能做的最好的就是O(n)：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1619220|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|code-block|syntax|javascript|1619221|如果问题是在同一数据集中重复获取最大(小于)不同n值的值，那么可能有一种解决方案是使用桶分类将列表按O(n)排序，然后重复使用bisect。|offset|length|style|CODE|1619222|entityMap|0|LINK|mutability|MUTABLE|url|http://www.geekviewpoint.com/python/sorting/bucketsort|1|https://docs.python.org/2/library/bisect.html^0|0|0|O|1|1R|6|17|3|0|1R|6|1|0^^$0|@$1|2|3|4|5|6|7|W|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|X|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|Y|8|@$I|Z|J|10|K|L]|$I|11|J|12|K|L]]|9|@$I|13|J|14|1|15]|$I|16|J|17|1|18]]|A|$]]|$1|M|3|-4|5|6|7|19|8|@]|9|@]|A|$]]]|N|$O|$5|P|Q|R|A|$S|T]]|U|$5|P|Q|R|A|$S|V]]]]

If you can't make any assumptions about the ordering of the array, then I think the best you can do is O(n):

<pre><code>def largest_less_than(numlist, n):
 answer = min(numlist, key=lambda x: n-x if n&gt;=x else float('inf'))
 if answer &gt; n:
 answer = None
 return answer
</code></pre>

If the question is about repeatedly getting the largest-less-than for different <code>n</code> values on the same dataset, then maybe one solution is using <a href="http://www.geekviewpoint.com/python/sorting/bucketsort" rel="nofollow">bucket sort</a> to get your list sorted in O(n), and then use <a href="https://docs.python.org/2/library/bisect.html" rel="nofollow"><code>bisect</code></a> repeatedly.

blocks|key|2174424|text|您可以为此使用选择算法。下面我给出了一个简单的算法：|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|2174425|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+'+%2B+str(largest_number)
else:
++++print+'value+not+found'|code-block|syntax|javascript|2174426|entityMap|0|LINK|mutability|MUTABLE|url|https://en.wikipedia.org/wiki/Selection_algorithm^0|7|4|0|0|0^^$0|@$1|2|3|4|5|6|7|Q|8|@]|9|@$A|R|B|S|1|T]]|C|$]]|$1|D|3|E|5|F|7|U|8|@]|9|@]|C|$G|H]]|$1|I|3|-4|5|6|7|V|8|@]|9|@]|C|$]]]|J|$K|$5|L|M|N|C|$O|P]]]]

You can use the <a href="https://en.wikipedia.org/wiki/Selection_algorithm" rel="nofollow">selection algorithm</a> for this. Below I have provided a simple algorithm for this:

<pre><code>numbers = [1, 3, 7, 10]
n = 9
largest_number = None
for number in numbers: 
 if number&lt;=n:
 largest_number=number
 else:
 break

if largest_number:
 print 'value found ' + str(largest_number)
else:
 print 'value not found'
</code></pre>

blocks|key|1014141|text|如果您不需要支持列表中的动态添加和删除，那么只需对其进行排序，并使用二进制搜索来查找O(log+)时间内最大的|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1014142|1014143|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|E|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|F|8|@]|9|@]|A|$]]|$1|C|3|-4|5|6|7|G|8|@]|9|@]|A|$]]]|D|$]]

If you don't have to support dynamic additions and removals from the list, then just sort it and use binary search to find the largest &lt; n in O(log N) time.

blocks|key|2174474|text|梅尔尼克的回答可能是完成这个问题的正确方法。但是，由于HackerRank没有一种使用库的方法，下面是我用来解决这个问题的一个左倾红黑树的实现。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|2174475|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|code-block|syntax|javascript|2174476|entityMap|0|LINK|mutability|MUTABLE|url|https://en.wikipedia.org/wiki/Left-leaning_red%25E2%2580%2593black_tree^0|1R|5|0|0|0^^$0|@$1|2|3|4|5|6|7|Q|8|@]|9|@$A|R|B|S|1|T]]|C|$]]|$1|D|3|E|5|F|7|U|8|@]|9|@]|C|$G|H]]|$1|I|3|-4|5|6|7|V|8|@]|9|@]|C|$]]]|J|$K|$5|L|M|N|C|$O|P]]]]

ig-melnyk's answer is probably the right way to complete this question. But since HackerRank doesn't have a way to use libraries, here's an implementation of a <a href="https://en.wikipedia.org/wiki/Left-leaning_red%E2%80%93black_tree" rel="nofollow">Left-Leaning Red Black Tree</a> that I used for the problem.

<pre><code>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 &lt; 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 &lt; 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
</code></pre>

blocks|key|1014161|text|你可以减少你要找的号码，直到找到为止。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1014162|此函数将在fs中找到最大数<=+n的位置，这是一个排序的整数列表。|1014163|如果没有小于或等于n的数字，则返回-1。|1014164|def+findmaxpos(n):
++if+n+<+fs[0]:+return+-1++
++while+True:
++++if+n+in+fs:+return+fs.index(n)
++++n-=1|code-block|syntax|javascript|1014165|entityMap^0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|M|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|N|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|O|8|@]|9|@]|A|$]]|$1|F|3|G|5|H|7|P|8|@]|9|@]|A|$I|J]]|$1|K|3|-4|5|6|7|Q|8|@]|9|@]|A|$]]]|L|$]]

You can decrease the number you're looking for until found.

This funtion will find the position of the largest number &lt;= n in fs, a sorted list of integers.

If there are no numbers smaller or equal to n, it will return -1.

<pre><code>def findmaxpos(n):
 if n &lt; fs[0]: return -1 
 while True:
 if n in fs: return fs.index(n)
 n-=1

</code></pre>

I'm having trouble finding the following functionality in Python:

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

For example, given the list <code>[1, 3, 7, 10]</code> and <code>n = 9</code>, the function would return 7.

I'm looking for Python functionality similar to <a href="http://docs.oracle.com/javase/7/docs/api/java/util/TreeSet.html#lower(E)" rel="nofollow">Java's <code>TreeSet.lower</code></a>.

I can use another data structure. A heap seems appropriate.

The O(n) solution is too slow for the scale of the problem. I'm looking for an O(log n) solution.

<h3>Background</h3>

I'm working on <a href="https://www.hackerrank.com/challenges/maximise-sum" rel="nofollow">https://www.hackerrank.com/challenges/maximise-sum</a>. The possible values range from 1 - 10^14, so using a sorted list with binary search is too slow.

My current thought is to iterate on <a href="https://hg.python.org/cpython/file/2.7/Lib/heapq.py" rel="nofollow">Python's heapq backing array</a> directly. I was hoping there might be something more Pythonic.

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

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

教程

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云AI代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

功能1上新10个字符

功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符。

功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符。

功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符

功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符

功能4上新

文章&问答评论现已支持表情

全新交互，全新视觉，新增快捷键、悬浮工具栏、高亮块等功能并同时优化现有功能，全面提升创作效率和体验

社区富文本编辑器全新改版！诚邀体验～ 

精选全网热门MCP server，让你的AI更好用 🚀

💥开发者 MCP广场重磅上线！

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

聚焦“写作效率、视觉美观与运行性能”三方面进行全面升级，为您提供更高效、稳定的创作环境

社区富文本&Markdown编辑器全新改版上线，欢迎大家体验!

诚挚邀请您参与本次调研，分享您的真实使用感受与建议。您的反馈至关重要，感谢您的支持与参与！

社区新版编辑器体验调研

我很难在Python中找到以下功能：给定一组数字，返回小于或等于n的最大数，如果不存在这样的数字，则返回None。例如，给定列表[1, 3, 7, 10]和n = 9，函数将返回7。我正在寻找类似于的Python功能。我可以使用另一种数据结构。一堆似乎是合适的。O(n)解对于问题的规模来说太慢了。我在找一个O(log )的解。背景我在做。可能的值范围为1-10^14，因此使用排序列表进行二进制搜索

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

回答 7

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

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

回答 7

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

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