草庐IT

python - 给定两个整数列表，在彼此距离 < O(N^2) 的范围内找到每一对

coder 2023-08-25 原文

我有两个排序的整数列表。我想分别从第一个和第二个列表中找到彼此之间一定距离内的所有整数对。

天真的方法是检查每一对，导致 O(N^2) 时间。我确信有一种方法可以在 O(N*logN) 或更短的时间内完成。

在 python 中，朴素的 O(N^2) 方法如下:

def find_items_within(list1, list2, within):
    for l1 in list1:
        for l2 in list2:
            if abs(l1 - l2) <= within:
                yield (l1, l2)

pythonic 答案加分。

应用说明

我只是想指出这个小谜题的目的。我正在搜索一份文档，并希望在另一个术语的特定距离内找到一个术语的所有出现。首先，您找到两个项的项向量，然后您可以使用下面描述的算法来确定它们是否在给定的彼此距离内。

最佳答案

没有比O(n^2) 更好的方法了。因为有 O(n^2)对，对于 within = infinity你需要放弃所有这些。

要找到这些对的数量是另一回事，可以通过找到每个元素的第一个索引来完成 e够了within-e < arr[idx] .索引idx例如可以使用二进制搜索有效地找到 - 这将为您提供 O(nlogn)找到这些对的数量的解决方案。

它也可以在线性时间 ( O(n) ) 内完成，因为您实际上不需要在第一个 [a,b] 之后对所有元素进行二进制搜索。找到范围，注意彼此范围[a',b'] - 如果 a>a'然后b>=b' - 所以你实际上需要用两个指针迭代列表并“永不回头”以获得线性时间复杂度。

伪代码:(线性时间求解)

numPairs <- 0
i <- 0
a <- 0
b <- 0
while (i < list1.length):
  while (a < i && list1[i] - list2[a] > within):
      a <- a+1
  while (b < list2.length && list2[b] - list1[i] < within):
      b <- b+1
  if (b > a):
      numPairs <- numPairs + (b-a)
  i <- i+1
return numPairs

(我从最初的伪代码中做了一些修正——因为第一个伪代码的目的是在单个列表中找到范围内的对数——而不是两个列表之间的匹配，对此感到抱歉)

关于python - 给定两个整数列表，在彼此距离 < O(N^2) 的范围内找到每一对，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13627711/

给定彼此codesectionlistpythonalgorithm

有关python - 给定两个整数列表，在彼此距离 < O(N^2) 的范围内找到每一对的更多相关文章

  1. python - 如何使用 Ruby 或 Python 创建一系列高音调和低音调的蜂鸣声？ - 2

    关闭。这个问题是opinion-based.它目前不接受答案。想要改进这个问题？更新问题，以便editingthispost可以用事实和引用来回答它.关闭4年前。Improvethisquestion我想在固定时间创建一系列低音和高音调的哔哔声。例如:在150毫秒时发出高音调的蜂鸣声在151毫秒时发出低音调的蜂鸣声200毫秒时发出低音调的蜂鸣声250毫秒的高音调蜂鸣声有没有办法在Ruby或Python中做到这一点？我真的不在乎输出编码是什么(.wav、.mp3、.ogg等等)，但我确实想创建一个输出文件。

  2. ruby-on-rails - 如何从 format.xml 中删除 <hash></hash> - 2

    我有一个对象has_many应呈现为xml的子对象。这不是问题。我的问题是我创建了一个Hash包含此数据，就像解析器需要它一样。但是rails自动将整个文件包含在.........我需要摆脱type="array"和我该如何处理？我没有在文档中找到任何内容。 最佳答案 我遇到了同样的问题；这是我的XML:我在用这个:entries.to_xml将散列数据转换为XML，但这会将条目的数据包装到中所以我修改了:entries.to_xml(root:"Contacts")但这仍然将转换后的XML包装在“联系人”中，将我的XML代码修改为

  3. ruby-on-rails - 如何在 ruby​​ 中使用两个参数异步运行 exe？ - 2

    exe应该在我打开页面时运行。异步进程需要运行。有什么方法可以在ruby​​中使用两个参数异步运行exe吗？我已经尝试过ruby​​命令-system()、exec()但它正在等待过程完成。我需要用参数启动exe，无需等待进程完成是否有任何ruby​​gems会支持我的问题？ 最佳答案 您可以使用Process.spawn和Process.wait2:pid=Process.spawn'your.exe','--option'#Later...pid,status=Process.wait2pid您的程序将作为解释器的子进程执行。除

  4. ruby - RVM 使用列表[0] - 2

    是否有类似“RVMuse1”或“RVMuselist[0]”之类的内容而不是键入整个版本号。在任何时候，我们都会看到一个可能包含5个或更多ruby的列表，我们可以轻松地键入一个数字而不是X.X.X。这也有助于rvmgemset。 最佳答案 这在RVM2.0中是可能的=>https://docs.google.com/document/d/1xW9GeEpLOWPcddDg_hOPvK4oeLxJmU3Q5FiCNT7nTAc/edit?usp=sharing-知道链接的任何人都可以发表评论

  5. ruby-on-rails - Nokogiri:使用 XPath 搜索 <div> - 2

    我使用Nokogiri(Rubygem)css搜索寻找某些在我的html里面。看起来Nokogiri的css搜索不喜欢正则表达式。我想切换到Nokogiri的xpath搜索，因为这似乎支持搜索字符串中的正则表达式。如何在xpath搜索中实现下面提到的(伪)css搜索？require'rubygems'require'nokogiri'value=Nokogiri::HTML.parse(ABBlaCD3"HTML_END#my_blockisgivenmy_bl="1"#my_eqcorrespondstothisregexmy_eq="\/[0-9]+\/"#FIXMEThefoll

  6. ruby - 这两个 Ruby 类初始化定义有什么区别？ - 2

    我正在阅读一本关于Ruby的书，作者在编写类初始化定义时使用的形式与他在本书前几节中使用的形式略有不同。它看起来像这样:classTicketattr_accessor:venue,:datedefinitialize(venue,date)self.venue=venueself.date=dateendend在本书的前几节中，它的定义如下:classTicketattr_accessor:venue,:datedefinitialize(venue,date)@venue=venue@date=dateendend在第一个示例中使用setter方法与在第二个示例中使用实例变量之间是

  7. Python 相当于 Perl/Ruby ||= - 2

    这个问题在这里已经有了答案:关闭10年前。PossibleDuplicate:Pythonconditionalassignmentoperator对于这样一个简单的问题表示歉意，但是谷歌搜索||=并不是很有帮助；)Python中是否有与Ruby和Perl中的||=语句等效的语句？例如:foo="hey"foo||="what"#assignfooifit'sundefined#fooisstill"hey"bar||="yeah"#baris"yeah"另外，类似这样的东西的通用术语是什么？条件分配是我的第一个猜测，但Wikipediapage跟我想的不太一样。

  8. ruby-on-rails - capybara ::ElementNotFound:无法找到 xpath "/html" - 2

    我正在学习http://ruby.railstutorial.org/chapters/static-pages上的RubyonRails教程并遇到以下错误StaticPagesHomepageshouldhavethecontent'SampleApp'Failure/Error:page.shouldhave_content('SampleApp')Capybara::ElementNotFound:Unabletofindxpath"/html"#(eval):2:in`text'#./spec/requests/static_pages_spec.rb:7:in`(root)'

  9. java - 什么相当于 ruby​​ 的 rack 或 python 的 Java wsgi？ - 2

    什么是ruby​​的rack或python的Java的wsgi？还有一个路由库。 最佳答案 来自Python标准PEP333:Bycontrast,althoughJavahasjustasmanywebapplicationframeworksavailable,Java's"servlet"APImakesitpossibleforapplicationswrittenwithanyJavawebapplicationframeworktoruninanywebserverthatsupportstheservletAPI.ht

  10. 华为OD机试用Python实现 -【明明的随机数】 2023Q1A - 2

    华为OD机试题本篇题目：明明的随机数题目输入描述输出描述：示例1输入输出说明代码编写思路最近更新的博客华为od2023|什么是华为od，od薪资待遇，od机试题清单华为OD机试真题大全，用Python解华为机试题|机试宝典【华为OD机试】全流程解析+经验分享,题型分享,防作弊指南华为o

随机推荐