用于计算数组C ++中相同数字的函数

Question

我有这个函数，应该计算在某个数组中出现多少相同数量的重复项。重要的是，这必须是复杂度O（logn）。我在下面写了这个，但它没有正确计算重复。还有一件事，数字从最低到最高排序。

int CountElementsinFile(int *Arr, int num, int numOfD)
{
    int avg{}; 
    int inB = 0; 
    int inE = numOfD - 1; 
    int el{};
    while (inB <= inE)
    {
        avg = (inB + inE) / 2;

        if (Arr[avg] == num)
            el++;
            if (Arr[avg] > num)
                inE = avg - 1;
            else
                inB = avg + 1;
    }

    return el;
}

Answer 1

使用std，您可能会：

int CountElementsinFile(const int *a, int size, int value)
{
    const auto range = std::equal_range(a, a + size, value);
    return range.second - range.first;
}

Answer 2

您需要使用num确定Bisection method子序列的上下边界。您需要重新排列while循环中的下部或上部（取决于比较）搜索区域边界，直到inB < inE将区域缩小一半。复杂性将是O(ln(n))。你很接近，但你不能在一个while循环中找到两个边界。我刚刚纠正了你的代码。

int CountElementsinFile(int *Arr, int num, int numOfD)
{
   // There is no num in the array
   if (Arr[0] > num || Arr[numOfD - 1] < num)
      return 0;

   int avg{};
   int lb, ub;

   // Find lower boundary
   int inB = 0;
   int inE = numOfD - 1;
   while (inB < inE)
   {
      // divide search region
      avg = (inB + inE) / 2;
      if (Arr[avg] >= num)
         inE = avg;
      else
         inB = avg+1;
   }

   lb = inE;

   // Find upper boundary   
   // inB already found
   inE = numOfD - 1;
   while (inB < inE)
   {
      avg = (inB + inE + 1) / 2;
      if (Arr[avg] > num)
         inE = avg-1;
      else
         inB = avg;
   }

   ub = inB;

   return ub - lb + 1;
}

int main()
{
   int arr[] = { 5, 7, 8, 9, 9, 9, 9, 9, 11 };
   std::cout << CountElementsinFile(arr, 9, sizeof(arr) / sizeof(int)) << std::endl;
   return 0;
}

Answer 3

从你给出的函数签名，我猜你得到了一个数字N和一个排序的数字数组，需要计算N出现在数组中的次数。

由于数组是排序的，你需要找到小于N的第一个数字的索引（使用二进制搜索）（这是O(log n)），第一个数字的索引大于N（这也是O(log n)），简单地说从另一个中减去一个索引。当然，你需要考虑没有小于N或大于N的数字的边缘情况，但这是你需要弄清楚的。

Answer 4

#include<algorithm>
using namespace std;

int CountElementsinFile(int arr[], int size, int numToSearch)
{
    return count(arr, arr + size, numToSearch); 
}