Codility 性能差异：数组与哈希

Question

我做了一个 codility 测试：https://codility.com/programmers/lessons/2-arrays/odd_occurrences_in_array/ 我注意到两种不同解决方案之间的性能差异：

1 - 列出解决方案：

def solution(list)
  unmatched_elements = []
  list.each{ |el|
    if unmatched_elements.include? el
      unmatched_elements.delete el
    else
      unmatched_elements.push el
    end
  }
  unmatched_elements[0]
end

2 - 哈希解决方案

def solution(a)
  unmatch = {}

  a.each do |e|
    if unmatch[e].nil?
      unmatch[e] = 1
    else
      unmatch.delete e
    end
  end
  unmatch.keys.first
end

第一个给了我 25% 的性能分数，但有一些超时。第二个给了我 100% 的性能分数。这是为什么？我认为推送到哈希会导致 O(n) space 复杂度，就像列表一样，但似乎不是，为什么？

Answer 1

这与 space 复杂度无关，与时间复杂度有关。具体来说，在数组 (include?) 中查找元素是 N 次操作，因为它需要检查每个元素直到找到匹配项。哈希查找 [] 是常数时间。

这个答案解释了为什么 Hash 的搜索时间为 O(1)：

Codility 性能差异：数组与哈希

Codility performance difference: array vs hash

ruby

performance

big-o