属于同一持续时间的元素

Question

给定一个以微秒为单位的排序时间戳向量，我需要确定属于相同持续时间（例如秒）的元素的大小。

我的想法是迭代向量，直到属于同一持续时间的最后一个元素，对每个元素执行此操作并返回最大子向量的大小。

有没有更聪明的想法（时间复杂度较低）？

Answer 1

我希望那些发表评论的人会提出类似以下的建议。这是 Ruby 代码，但不懂 Ruby 的读者可以将其视为伪代码，并且理解它应该没有困难，特别是因为我已经显示了中间计算的结果。

假设

arr = [1, 1, 3, 5, 5, 6, 6, 6, 6, 8, 8, 9, 9, 9]

“当前索引”将始终指向组中的第一个值。在此示例中，它将采用值

0

（第一个

1

）、

2

（第一个

3

）、

3

（第一个

5

）、

5

（第一个

6

） )、

9

（第一个

8

）和

11

（第一个

9

）。

方法

bsearch_index

执行二分搜索以返回相对于当前索引的下一个更高值的索引。例如，如果当前索引是

3

（第一个

5

），

bsearch_index

将返回

5

（第一个

6

）。如果没有比当前索引更大的值（这里当当前索引为

11

时，指向第一个

9

），

bsearch_index

返回

nil

，并且可以在代码。

best = { :val=>nil, :len=>-Float::INFINITY }
curr_idx = 0
curr_val = arr[curr_idx]

arr.each do |x|
  puts
  puts "x = #{x}, curr_idx = #{curr_idx}, curr_val = #{curr_val}, best = #{best}"
  i = arr.bsearch_index { |x| x > curr_val }  
  i = arr.size if i.nil?
  puts "i from bsearch_idx = #{i}"

  diff = i - curr_idx
  puts "diff = #{diff}"

  if diff > best[:len]
    puts "best updated"
    best = { :val=>curr_val, :len=>diff }
  end

  break if i == arr.size
  curr_idx = i
  curr_val = arr[curr_idx]
end

puts
puts best

显示以下内容。

x = 1, curr_idx = 0, curr_val = 1, best = {:val=>nil, :len=>-Infinity}
i from bsearch_idx = 2
diff = 2
best updated

x = 1, curr_idx = 2, curr_val = 3, best = {:val=>1, :len=>2}
i from bsearch_idx = 3
diff = 1

x = 3, curr_idx = 3, curr_val = 5, best = {:val=>1, :len=>2}
i from bsearch_idx = 5
diff = 2

x = 5, curr_idx = 5, curr_val = 6, best = {:val=>1, :len=>2}
i from bsearch_idx = 9
diff = 4
best updated

x = 5, curr_idx = 9, curr_val = 8, best = {:val=>6, :len=>4}
i from bsearch_idx = 11
diff = 2

x = 6, curr_idx = 11, curr_val = 9, best = {:val=>6, :len=>4}
i from bsearch_idx = 14
diff = 3

{:val=>6, :len=>4}

可以根据

[6, 6, 6, 6]

的最终值轻松构造所需的数组

best

。

当每个值有多个实例时，二分搜索效果很好。另一方面，如果有许多不同的值并且每个值的实例很少，那么简单地枚举数组可能会更快，从而避免执行二分搜索所涉及的开销。