分隔并征服算法以计数数组中元素的出现而不对其进行排序

Question

我和朋友正在讨论我们是否可以使用鸿沟和征服算法在不分类数组的情况下使用divide and Conlay算法出现了多少个特定元素k？

我们达到了一个封锁，如果我们使用二进制搜索，一旦找到元素一次，它就会停止。有什么想法吗？

Answer 1

正如其中一条评论所提到的那样，二进制搜索用于在分类数组中找到一个元素，而在您的问题中似乎并非如此。

一个简单的划分和征服算法是将数组分成较小的部分并解决它们的问题。例如，如果算法的输入是和value k的数组，则可以编写一个将数组除以两个的函数，并计算每个数字的出现数量部分然后将它们添加在一起。

此功能采用左和右值，该值是给定向量中的索引。最初，此功能使用left = 0和right = in.size（）：

int NumberOfOccurances(const vector<int> &in, int k, 
                       int left, int right){
   // Base case when the size of the array is 1:
   if(right - left==1){
     return in[0] == k ? 1 : 0;
   } else {
     // Otherwise, break it into two subproblems.
     int mid = (left + right) / 2;
     return NumberOfOccurances(in, k, left, mid) +
            NumberOfOccurances(in, k, mid, right)
   }
}

而不是除以2，您也可以除以3，4或其他整数价值。