有效计算已排序数组中键的出现次数的方法

Question

这是在微软的现场采访中提出的.

计算数组中给定键的出现次数.

我回答了线性搜索,因为元素可能散布在数组中.说密钥在开头和结尾都有.所以我们需要扫描整个阵列.

接下来他询问阵列是否排序？

想了一会儿说我会再次使用线性搜索.因为密钥的重复(如果存在)可以在阵列中的任何位置.作为优化,我还说如果第一个和最后一个数组元素相同,你可以将数组长度作为答案.

在这两种情况下,我的分析是否正确？

例:

Input = [0 0 1 1 1 2 2 3 3], key = 1, Answer = 3
Input = [0 0 2 2 3 3],       key = 1, Answer = 0

Answer 1

对于未排序的数组,我们除了线性搜索之外没有太多可以做的事情.

对于排序数组,您可以O(logN)使用稍微修改的二进制搜索来执行此操作:

• 找到第一次出现的索引 key,调用它f.
• 找到最后一次出现的索引 key,调用它l.
• 如果key数组中存在l-f+1 则是答案.

找到第一次出现:

arr[i]是keyiff 的第一次出现

• arr[i] == key 而无论是
  • i == 0(它是数组的第一个元素)或
  • arr[i-1] != key (它不是数组的第一个元素,左边的元素是不同的)

您可以稍微修改二进制搜索以查找第一个匹配项.
在二进制搜索中,您会在找到时终止搜索arr[mid] == key.
修改条件,以便在找到第一个匹配项而不是任何匹配项时终止搜索.

算法:

low = 0
high = arrSize - 1 

while low <=  high

  mid = (low + high) / 2

  //if arr[mid] == key         // CHANGE
  if arr[mid] == key AND ( mid == 0 OR arr[mid-1] != key )
    return mid
  //else if ( key < arr[mid] ) // CHANGE
  else if ( key <= arr[mid] ) 
    high = mid - 1
  else
    low = mid + 1        
  end-if

end-while

return -1

同样,您可以找到最后一次出现.

Answer 2

这一次,我将提出一个C++实现.

size_t count(std::vector<int> const& vec, int key)
{
  auto p = std::equal_range(vec.begin(), vec.end(), key);
  return std::distance(p.first, p.second);
}

equal_range 使用二进制搜索,结果相当于:

std::make_pair(std::lower_bound(vec.begin(), vec.end(), key),
               std::upper_bound(vec.begin(), vec.end(), key);

但是实现应该使它稍微快一些,即使它们都在O(log N)中(就比较数而言).

Answer 3

如果数组未排序，是的，从一端到另一端的线性搜索是最好的。

但是，如果数组已排序，则可以通过应用二分或插值搜索技术比线性时间做得更好。

将问题视为与“在排序列表中查找数字 X”相同，并添加“然后左右扫描以确定 X 出现的次数”的详细信息。第一部分，即搜索，在大多数情况下最好使用二分搜索或插值搜索来完成。

http://en.wikipedia.org/wiki/Interpolation_search

http://en.wikipedia.org/wiki/Binary_search