Функция для подсчета одинаковых чисел в массиве C ++ - PullRequest
Новая
       17

Функция для подсчета одинаковых чисел в массиве C ++

2 голосов
/ 13 марта 2019

У меня есть эта функция, которая должна подсчитывать, сколько дубликатов с одинаковым номером встречается в определенном массиве.Важно, что это должно быть сложности 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;
}

Ответы [ 4 ]

2 голосов
/ 13 марта 2019

С помощью 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;
}
2 голосов
/ 13 марта 2019

Вам нужно определить верхнюю и нижнюю границы подпоследовательности num, используя метод Бисекция .Вам нужно переставить нижнюю или верхнюю (в зависимости от сравнения) границу области поиска в цикле 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;
}
0 голосов
/ 13 марта 2019 
#include<algorithm>
using namespace std;

int CountElementsinFile(int arr[], int size, int numToSearch)
{
    return count(arr, arr + size, numToSearch); 
}
0 голосов
/ 13 марта 2019

Из подписи функции, которую вы дали, я предполагаю, что вам дали число N и отсортированный массив чисел, и вам нужно подсчитать, сколько раз N появляется в массиве.

Поскольку массив отсортирован, вам нужно найти индекс (используя бинарный поиск) первого числа, которое меньше N (это O(log n)), индекс первого числа, большего чем N (это также O(log n)), и просто вычтите один индекс из другого. Конечно, вам нужно принять во внимание крайние случаи, когда нет чисел, меньших чем N или больше, чем N, но это вам нужно выяснить.

...