3

检查列表中的至少一个数字是否在其他列表的一个范围内的一种可能方法如下：

# Input example:
# numbers = [123, 345, 567]
# ranges =[(1..10), (60..80), (200..400)]
def is_in(numbers, ranges)
  numbers.each do |n|
    ranges.each do |r|
      return true if r.include?(n)
    end
  end
  false
end

对于每种情况，最快的方法是什么：

  1. 只有数字列表很大
  2. 只有范围列表很大
  3. 两个都大
4

3 回答 3

3

Array#bsearch如果您的数字数组很大并且是有序的，您可以使用 Ruby 2.0 的新二进制搜索方法将范围覆盖检查从 O(N) 复杂度加速到 O(logN) 。

class Range
  def fast_cover_any?(ordered_arr)
    lo = first
    probe = ordered_arr.bsearch {|x| x >= lo}
    probe && exclude_end? ? probe < last : probe <= last
  end
end

ranges.any? { |r| r.fast_cover_any?(numbers) }
于 2013-04-30T20:35:26.950 回答
1 
ranges =[(1..10), (60..80), (200..400)]

numbers = [123, 700, 567]
numbers.any?{|x| ranges.any? {|y| y.include? x}} #=> false

numbers = [123, 400, 567]
numbers.any?{|x| ranges.any? {|y| y.include? x}} #=> true

使用ordered list：

ranges =[(1..10), (60..80), (200..400)]

numbers = [123, 300, 567]
p numbers.sort.any?{|y| ranges.sort_by(&:first).bsearch{|x| x.include? y}} #=> true

numbers = [123, 700, 567]
p numbers.sort.any?{|y| ranges.sort_by(&:first).bsearch{|x| x.include? y}} #=> false
于 2013-04-30T20:00:36.263 回答
1

简单的答案是将其中一个数据结构存储在有组织的结构中，然后搜索另一个列表的元素。

假设您有两个长度分别为 m 和 n 的列表 x 和 y。

如果 m << n：对 x 进行排序，并在排序列表中从 y 中查找元素

如果 m >> n：对 y 进行排序，并在排序列表中从 x 中查找元素

如果它们大小相同，请选择其中任何一个进行排序。

如何组织范围：使用每个范围的开头对列表进行排序。如果两个范围重叠合并它们。最后，您将获得一个根据范围开始排序的非重叠范围列表。

于 2013-04-30T20:28:21.693 回答