一种有效的方法来计算排序数组中键的出现 [英] Efficient way to count occurrences of a key in a sorted array

问题描述

这是在Microsoft现场采访中问到的。

This was asked in on-site Microsoft interview.

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

Count the number of occurrences of a given key in an array.

我回答了线性搜索，因为元素可能分散在
数组中。假设在开头和结尾都找到了密钥。所以我们
需要扫描整个数组。

I answered linear search because the elements may be scattered in the array. Say the key is found in the beginning and at the end. So we need to scan the entire array.

接下来他问数组是否排序了？

Next he asked what if the array is sorted?

想了一会儿，然后说我将再次使用线性搜索。因为键的
重复（如果存在）可以在数组中的任何位置。作为
的优化，我还说过，如果第一个和最后一个数组元素相同，则
可以将数组长度作为答案。

Thought for a while and said I'll use linear search again. Because the repetitions of the key if present can be anywhere in the array. As an optimization I also said if first and last array elements are same you can take the array length as the answer.

我的分析是

示例：

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

推荐答案

对于未排序的数组，除了线性搜索外，我们无能为力。

For unsorted array there is not much we can do other than linear search.

对于排序数组，您可以使用稍微修改的二进制搜索在 O（logN）中进行：

For sorted array you can do it in O(logN) using a slightly modified binary search:

• 找到第一次出现的
  key 的索引，将其称为 f 。


• 找到最后一次出现的
  key 的索引，将其称为 l 。


• 如果键存在于数组 l-f中+1
  是答案。

• Find the index of first occurrence of key, call it f.
• Find the index of last occurrence of key, call it l.
• If the key exists in the array l-f+1 is the answer.

找到第一次出现的地方：

Finding the first occurrence:

arr [i] i s第一次出现 key iff

arr[i] is the first occurrence of key iff

• arr [ i] ==键 和
  
  
  
  
  • i == 0 （这是
    数组的第一个元素）或
  
  
  • arr [i-1] ！=键（这不是数组的第一个
    元素，而它与
    的元素是不同的）
  
  
  • arr[i] == key and either
    • i == 0 ( it's the first element of the array) or
    • arr[i-1] != key (it's not the first element of the array and element to it's left is different)

    您可以略微修改二进制搜索以找到第一个匹配项。
    在二进制搜索中，当找到<$ c时终止搜索$ c> arr [mid] ==键。
    修改条件，以便在发现 first 事件时终止搜索而不是 任何 出现。

    You can slightly modify the binary search to find the first occurrence.
    In a binary search you terminate the search when you find arr[mid] == key.
    Modify the condition such that you terminate the search when you find the first occurrence instead of any occurrence.

    算法：

    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
    

    类似地，您可以找到最后一次出现。

    Similarly you can find the last occurrence.

    这篇关于一种有效的方法来计算排序数组中键的出现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！