Рубрики

Подсчет количества вхождений (или частоты) в отсортированном массиве

Учитывая отсортированный массив arr [] и число x, напишите функцию, которая подсчитывает вхождения x в arr []. Ожидаемая сложность времени O (Logn)

Примеры:

  Input: arr[] = {1, 1, 2, 2, 2, 2, 3,},   x = 2
  Output: 4 // x (or 2) occurs 4 times in arr[]

  Input: arr[] = {1, 1, 2, 2, 2, 2, 3,},   x = 3
  Output: 1 

  Input: arr[] = {1, 1, 2, 2, 2, 2, 3,},   x = 1
  Output: 2 

  Input: arr[] = {1, 1, 2, 2, 2, 2, 3,},   x = 4
  Output: -1 // 4 doesn't occur in arr[] 

Метод 1 (линейный поиск)
Линейно ищите x, подсчитывайте вхождения x и возвращайте счет.

C ++

// C ++ программа для подсчета вхождений элемента
#include<bits/stdc++.h>

using namespace std;

  
// Возвращает количество раз, когда x встречается в arr [0..n-1]

int countOccurrences(int arr[], int n, int x)

{

    int res = 0;

    for (int i=0; i<n; i++)

        if (x == arr[i])

          res++;

    return res;

}

  
// Код драйвера

int main()

{

    int arr[] = {1, 2, 2, 2, 2, 3, 4, 7 ,8 ,8 };

    int n = sizeof(arr)/sizeof(arr[0]);

    int x = 2;

    cout << countOccurrences(arr, n, x);

    return 0;

}

Джава

// Java-программа для подсчета вхождений
// элемента

  

class Main

{

    // Возвращает количество раз, когда x встречается в arr [0..n-1]

    static int countOccurrences(int arr[], int n, int x)

    {

        int res = 0;

        for (int i=0; i<n; i++)

            if (x == arr[i])

              res++;

        return res;

    }

      

    public static void main(String args[])

    {

        int arr[] = {1, 2, 2, 2, 2, 3, 4, 7 ,8 ,8 };

        int n = arr.length;

        int x = 2;

        System.out.println(countOccurrences(arr, n, x));

    }

}

python3

# Python3 программа для подсчета
# вхождения элемента

  
# Возвращает количество раз x
# встречается в arr [0..n-1]

def countOccurrences(arr, n, x):

    res = 0

    for i in range(n):

        if x == arr[i]:

            res += 1

    return res

   
# Код драйвера

arr = [1, 2, 2, 2, 2, 3, 4, 7 ,8 ,8]

n = len(arr)

x = 2

print (countOccurrences(arr, n, x))

C #

// C # программа для подсчета вхождений
// элемента

using System;

  

class GFG

{

    // Возвращает количество раз x

    // встречается в arr [0..n-1]

    static int countOccurrences(int []arr,

                                int n, int x)

    {

        int res = 0;

          

        for (int i = 0; i < n; i++)

            if (x == arr[i])

            res++;

              

        return res;

    }

      

    // код драйвера

    public static void Main()

    {

        int []arr = {1, 2, 2, 2, 2, 3, 4, 7 ,8 ,8 };

        int n = arr.Length;

        int x = 2;

          

        Console.Write(countOccurrences(arr, n, x));

    }

}

  
// Этот код предоставлен Sam007

PHP

<?php
// PHP программа для подсчета вхождений
// элемента

  
// Возвращает количество раз x
// встречается в arr [0..n-1]

function countOccurrences($arr, $n, $x)

{

    $res = 0;

    for ($i = 0; $i < $n; $i++)

        if ($x == $arr[$i])

        $res++;

    return $res;

}

  

    // Код драйвера

    $arr = array(1, 2, 2, 2, 2, 3, 4, 7 ,8 ,8 );

    $n = count($arr);

    $x = 2;

    echo countOccurrences($arr,$n, $x);

      
// Этот код предоставлен Sam007
?>


Выход :

4

Сложность времени: O (n)

Способ 2 (лучше с помощью бинарного поиска)
Сначала мы находим вхождение, используя бинарный поиск. Затем мы подходим к левой и правой сторонам найденного индекса.

C ++

// C ++ программа для подсчета вхождений элемента
#include <bits/stdc++.h>

using namespace std;

  
// Рекурсивная функция двоичного поиска. Возвращается
// расположение x в заданном массиве arr [l..r] присутствует,
// иначе -1

int binarySearch(int arr[], int l, int r, int x)

{

    if (r < l)

        return -1;

  

    int mid = l + (r - l) / 2;

  

    // Если элемент присутствует посередине

    // сам

    if (arr[mid] == x)

        return mid;

  

    // Если элемент меньше среднего, то

    // он может присутствовать только в левом подмассиве

    if (arr[mid] > x)

        return binarySearch(arr, l, mid - 1, x);

  

    // иначе элемент может присутствовать только

    // в правом подмассиве

    return binarySearch(arr, mid + 1, r, x);

}

  
// Возвращает количество раз, когда x встречается в arr [0..n-1]

int countOccurrences(int arr[], int n, int x)

{

    int ind = binarySearch(arr, 0, n - 1, x);

  

    // Если элемента нет

    if (ind == -1)

        return 0;

  

    // Подсчитать элементы на левой стороне.

    int count = 1;

    int left = ind - 1;

    while (left >= 0 && arr[left] == x)

        count++, left--;

  

    // Подсчитать элементы на правой стороне.

    int right = ind + 1;

    while (right < n && arr[right] == x)

        count++, right++;

  

    return count;

}

  
// Код драйвера

int main()

{

    int arr[] = { 1, 2, 2, 2, 2, 3, 4, 7, 8, 8 };

    int n = sizeof(arr) / sizeof(arr[0]);

    int x = 2;

    cout << countOccurrences(arr, n, x);

    return 0;

}

Джава

// Java-программа для подсчета
// вхождения элемента

class GFG 

{

  

    // Рекурсивный бинарный поиск

    // функция. Возвращает местоположение

    // х в данном массиве arr [l..r]

    // присутствует, иначе -1

    static int binarySearch(int arr[], int l,

                            int r, int x)

    {

        if (r < l)

            return -1;

  

        int mid = l + (r - l) / 2;

  

        // Если элемент присутствует

        // в середине

        if (arr[mid] == x)

            return mid;

  

        // Если элемент меньше чем

        // середина, тогда это может быть только

        // присутствует в левом подмассиве

        if (arr[mid] > x)

            return binarySearch(arr, l, 

                                mid - 1, x);

  

        // иначе элемент может

        // присутствовать только в

        // правый подмассив

        return binarySearch(arr, mid + 1, r, x);

    }

  

    // Возвращает количество раз x

    // встречается в arr [0..n-1]

    static int countOccurrences(int arr[], 

                                int n, int x)

    {

        int ind = binarySearch(arr, 0

                               n - 1, x);

  

        // Если элемента нет

        if (ind == -1)

            return 0;

  

        // Подсчитать элементы на левой стороне.

        int count = 1;

        int left = ind - 1;

        while (left >= 0 && 

               arr[left] == x)

        {

            count++;

            left--;

        }

  

        // Подсчитать элементы

        // на правой стороне.

        int right = ind + 1;

        while (right < n && 

               arr[right] == x)

        {

            count++;

            right++;

        }

  

        return count;

    }

  

  

    // Код драйвера

    public static void main(String[] args) 

    {

        int arr[] = {1, 2, 2, 2, 2

                     3, 4, 7, 8, 8};

        int n = arr.length;

        int x = 2;

        System.out.print(countOccurrences(arr, n, x));

    }

}

  
// Этот код добавлен
// ChitraNayal

Python 3

# Python 3 программа для подсчета
# вхождения элемента

  
# Рекурсивный бинарный поиск
# функция. Возвращает местоположение
# x в данном массиве arr [l..r]
# присутствует, иначе -1

def binarySearch(arr, l, r, x):

    if (r < l):

        return -1

  

    mid = int( l + (r - l) / 2)

  

    # Если элемент присутствует

    # в середине

    if arr[mid] == x:

        return mid

  

    # Если элемент меньше чем

    # середина, тогда это может быть только

    # присутствует в левом подмассиве

    if arr[mid] > x:

        return binarySearch(arr, l, 

                            mid - 1, x)

  

    # Еще элемент

    # может присутствовать только

    # в правом подмассиве

    return binarySearch(arr, mid + 1,

                                r, x)

  
# Возвращает количество раз
# x встречается в arr [0..n-1]

def countOccurrences(arr, n, x):

    ind = binarySearch(arr, 0, n - 1, x)

  

    # Если элемента нет

    if ind == -1:

        return 0

  

    # Количество элементов

    # на левой стороне.

    count = 1

    left = ind - 1

    while (left >= 0 and 

           arr[left] == x):

        count += 1

        left -= 1

  

    Количество элементов на

    # правая сторона.

    right = ind + 1;

    while (right < n and

           arr[right] == x):

        count += 1

        right += 1

  

    return count

  
# Код драйвера

arr = [ 1, 2, 2, 2, 2

        3, 4, 7, 8, 8 ]

n = len(arr)

x = 2

print(countOccurrences(arr, n, x))

  
# Этот код добавлен
# by ChitraNayal

C #

// C # программа для подсчета
// вхождения элемента

using System;

  

class GFG 

{

  

    // Рекурсивный бинарный поиск

    // функция. Возвращает местоположение

    // х в данном массиве arr [l..r]

    // присутствует, иначе -1

    static int binarySearch(int[] arr, int l, 

                            int r, int x)

    {

        if (r < l)

            return -1;

  

        int mid = l + (r - l) / 2;

  

        // Если элемент присутствует

        // в середине

        if (arr[mid] == x)

            return mid;

  

        // Если элемент меньше чем

        // середина, тогда это может быть только

        // присутствует в левом подмассиве

        if (arr[mid] > x)

            return binarySearch(arr, l, 

                                mid - 1, x);

  

        // Остальное элемент

        // может присутствовать только

        // в правом подмассиве

        return binarySearch(arr, mid + 1,

                                   r, x);

    }

  

    // Возвращает количество раз x

    // встречается в arr [0..n-1]

    static int countOccurrences(int[] arr, 

                                int n, int x)

    {

        int ind = binarySearch(arr, 0, 

                               n - 1, x);

  

        // Если элемента нет

        if (ind == -1)

            return 0;

  

        // Подсчитать элементы на левой стороне.

        int count = 1;

        int left = ind - 1;

        while (left >= 0 && 

               arr[left] == x)

        {

            count++;

            left--;

        }

  

        // Подсчитать элементы на правой стороне.

        int right = ind + 1;

        while (right < n && 

               arr[right] == x)

        {

            count++;

            right++;

        }

  

        return count;

    }

  

  

    // Код драйвера

    public static void Main() 

    {

        int[] arr = {1, 2, 2, 2, 2, 

                     3, 4, 7, 8, 8};

        int n = arr.Length;

        int x = 2;

        Console.Write(countOccurrences(arr, n, x));

    }

}

  
// Этот код добавлен
// ChitraNayal

PHP

<?php 
// PHP-программа для подсчета
// вхождения элемента

  
// Рекурсивный бинарный поиск
// функция. Возвращает местоположение
// х в данном массиве arr [l..r]
// присутствует, иначе -1

function binarySearch(&$arr, $l

                         $r, $x)

{

    if ($r < $l)

        return -1;

  

    $mid = $l + ($r - $l) / 2;

  

    // Если элемент присутствует

    // в середине

    if ($arr[$mid] == $x)

        return $mid;

  

    // Если элемент меньше чем

    // середина, тогда это может быть только

    // присутствует в левом подмассиве

    if ($arr[$mid] > $x)

        return binarySearch($arr, $l,   

                            $mid - 1, $x);

  

    // Остальное элемент

    // может присутствовать только

    // в правом подмассиве

    return binarySearch($arr, $mid + 1, 

                                $r, $x);

}

  
// Возвращает количество раз
// x встречается в arr [0..n-1]

function countOccurrences($arr, $n, $x)

{

    $ind = binarySearch($arr, 0, 

                        $n - 1, $x);

  

    // Если элемента нет

    if ($ind == -1)

        return 0;

  

    // Подсчитать элементы

    // на левой стороне.

    $count = 1;

    $left = $ind - 1;

    while ($left >= 0 && 

           $arr[$left] == $x)

    

        $count++;

        $left--;

    }

      

    // Подсчитать элементы на правой стороне.

    $right = $ind + 1;

    while ($right < $n && 

           $arr[$right] == $x)

    {

        $count++;

        $right++;

    }

    return $count;

}

  
// Код драйвера

$arr = array( 1, 2, 2, 2, 2, 

              3, 4, 7, 8, 8 );

$n = sizeof($arr);

$x = 2;

echo countOccurrences($arr, $n, $x);

  
// Этот код добавлен
// ChitraNayal
?>


Выход :

4

Сложность времени: O (Log n + count), где count — количество вхождений.

Метод 3 (лучше всего использовать улучшенный бинарный поиск)
1) Используйте бинарный поиск, чтобы получить индекс первого вхождения x в arr []. Пусть индекс первого вхождения будет i.
2) Используйте двоичный поиск, чтобы получить индекс последнего вхождения x в arr []. Пусть индекс последнего вхождения будет j.
3) Возврат (j — i + 1);

C ++

// C ++ программа для подсчета вхождений элемента
// в отсортированном массиве.
# include <bits/stdc++.h>

using namespace std;

  
/ * если x присутствует в arr [], то возвращает счет

    вхождений x, в противном случае возвращает 0. * /

int count(int arr[], int x, int n)

{    

  / * получить индекс первого появления x * /

  int *low = lower_bound(arr, arr+n, x);

  

  // Если элемента нет, вернуть 0

  if (low == (arr + n) || *low != x)

     return 0;

     

  / * В противном случае получить индекс последнего вхождения x.

     Обратите внимание, что мы смотрим только в

     подмассив после первого появления * /   

  int *high = upper_bound(low, arr+n, x);     

     

  / * счетчик возврата * /

  return high - low;

}

  
/ * программа драйвера для проверки вышеуказанных функций * /

int main()

{

  int arr[] = {1, 2, 2, 3, 3, 3, 3};

  int x =  3;  // Элемент для подсчета в arr []

  int n = sizeof(arr)/sizeof(arr[0]);

  int c = count(arr, x, n);

  printf(" %d occurs %d times ", x, c);

  return 0;

}

С

# include <stdio.h>

  
/ * если x присутствует в arr [], то возвращает

   индекс ПЕРВОГО появления

   x в arr [0..n-1], иначе возвращает -1 * /

int first(int arr[], int low, int high, int x, int n)

{

  if(high >= low)

  {

    int mid = (low + high)/2;  / * низкий + (высокий - низкий) / 2; * /

    if( ( mid == 0 || x > arr[mid-1]) && arr[mid] == x)

      return mid;

    else if(x > arr[mid])

      return first(arr, (mid + 1), high, x, n);

    else

      return first(arr, low, (mid -1), x, n);

  }

  return -1;

}

  
/ * если x присутствует в arr [], то возвращает

   индекс LAST появления x в arr [0..n-1],

   в противном случае возвращает -1 * / 

int last(int arr[], int low, int high, int x, int n)

{

  if (high >= low)

  {

    int mid = (low + high)/2;  / * низкий + (высокий - низкий) / 2; * /

    if( ( mid == n-1 || x < arr[mid+1]) && arr[mid] == x )

      return mid;

    else if(x < arr[mid])

      return last(arr, low, (mid -1), x, n);

    else

      return last(arr, (mid + 1), high, x, n);      

  }

  return -1;

}

  
/ * если x присутствует в arr [], то возвращает счет

   вхождений x, в противном случае возвращает -1. * /

int count(int arr[], int x, int n)

{

  int i; // индекс первого появления x в arr [0..n-1]

  int j; // индекс последнего появления x в arr [0..n-1]

      

  / * получить индекс первого появления x * /

  i = first(arr, 0, n-1, x, n);

  

  / * Если x не существует в arr [], вернуть -1 * /

  if(i == -1)

    return i;

     

  / * В противном случае получить индекс последнего вхождения x.

     Обратите внимание, что мы смотрим только в подмассив

     после первого появления * /   

  j = last(arr, i, n-1, x, n);     

     

  / * счетчик возврата * /

  return j-i+1;

}

  
/ * программа драйвера для проверки вышеуказанных функций * /

int main()

{

  int arr[] = {1, 2, 2, 3, 3, 3, 3};

  int x =  3;  // Элемент для подсчета в arr []

  int n = sizeof(arr)/sizeof(arr[0]);

  int c = count(arr, x, n);

  printf(" %d occurs %d times ", x, c);

  getchar();

  return 0;

}

Джава

// Java-программа для подсчета вхождений
// элемента

  

class Main

{

    / * если x присутствует в arr [], то возвращает

       количество вхождений х,

       в противном случае возвращает -1. * /

    static int count(int arr[], int x, int n)

    {

      // индекс первого появления x в arr [0..n-1]

      int i; 

        

      // индекс последнего появления x в arr [0..n-1]

      int j; 

           

      / * получить индекс первого появления x * /

      i = first(arr, 0, n-1, x, n);

       

      / * Если x не существует в arr [], вернуть -1 * /

      if(i == -1)

        return i;

          

      / * В противном случае получить индекс последнего вхождения x.

         Обратите внимание, что мы смотрим только в

         подмассив после первого появления * /  

      j = last(arr, i, n-1, x, n);     

          

      / * счетчик возврата * /

      return j-i+1;

    }

       

    / * если x присутствует в arr [], то возвращает

       индекс ПЕРВОГО появления x в arr [0..n-1],

       в противном случае возвращает -1 * /

    static int first(int arr[], int low, int high, int x, int n)

    {

      if(high >= low)

      {

        / * низкий + (высокий - низкий) / 2; * /  

        int mid = (low + high)/2;  

        if( ( mid == 0 || x > arr[mid-1]) && arr[mid] == x)

          return mid;

        else if(x > arr[mid])

          return first(arr, (mid + 1), high, x, n);

        else

          return first(arr, low, (mid -1), x, n);

      }

      return -1;

    }

       

    / * если x присутствует в arr [], то возвращает

       индекс LAST появления x в arr [0..n-1],

       в противном случае возвращает -1 * /

    static int last(int arr[], int low, int high, int x, int n)

    {

      if(high >= low)

      {

        / * низкий + (высокий - низкий) / 2; * /      

        int mid = (low + high)/2

        if( ( mid == n-1 || x < arr[mid+1]) && arr[mid] == x )

          return mid;

        else if(x < arr[mid])

          return last(arr, low, (mid -1), x, n);

        else

          return last(arr, (mid + 1), high, x, n);      

      }

      return -1;

    }

       

    public static void main(String args[])

    {

        int arr[] = {1, 2, 2, 3, 3, 3, 3};

          

        // Элемент для подсчета в arr []

        int x =  3

        int n = arr.length;

        int c = count(arr, x, n);

        System.out.println(x+" occurs "+c+" times");

    }

}

python3

# Python3 программа для подсчета
# вхождения элемента

  
# если x присутствует в arr [], то
# возвращает количество вхождений
# x, в противном случае возвращает -1.

def count(arr, x, n):

  

    # получить индекс первого

    # появление x

    i = first(arr, 0, n-1, x, n)

   

    # Если х не существует в

    # arr [] затем вернуть -1

    if i == -1:

        return i

      

    # Остальное получить индекс последнего вхождения

    № х. Обратите внимание, что мы только ищем

    # в подмассиве после первого появления

    j = last(arr, i, n-1, x, n);     

      

    # возвращаемое количество

    return j-i+1;

  
# если x присутствует в arr [], вернуть
# индекс ПЕРВОГО появления x в
# arr [0..n-1], иначе возвращает -1

def first(arr, low, high, x, n):

    if high >= low:

  

        # низкий + (высокий - низкий) / 2

        mid = (low + high)//2      

          

    if (mid == 0 or x > arr[mid-1]) and arr[mid] == x:

        return mid

    elif x > arr[mid]:

        return first(arr, (mid + 1), high, x, n)

    else:

        return first(arr, low, (mid -1), x, n)

    return -1;

   
# если x присутствует в arr [], вернуть
# индекс LAST появления x
# в arr [0..n-1], иначе возвращает -1

def last(arr, low, high, x, n):

    if high >= low:

  

        # низкий + (высокий - низкий) / 2

        mid = (low + high)//2

   

    if(mid == n-1 or x < arr[mid+1]) and arr[mid] == x :

        return mid

    elif x < arr[mid]:

        return last(arr, low, (mid -1), x, n)

    else:

        return last(arr, (mid + 1), high, x, n)     

    return -1

  
# драйверная программа для проверки вышеуказанных функций

arr = [1, 2, 2, 3, 3, 3, 3]

x = 3  # Элемент для подсчета в arr []

n = len(arr)

c = count(arr, x, n)

print ("%d occurs %d times "%(x, c))

C #

// C # программа для подсчета вхождений
// элемента

using System;

  

class GFG

{

      

    / * если x присутствует в arr [], то возвращает

    количество вхождений х,

    в противном случае возвращает -1. * /

    static int count(int []arr, int x, int n)

    {

    // индекс первого появления x в arr [0..n-1]

    int i; 

          

    // индекс последнего появления x в arr [0..n-1]

    int j; 

          

    / * получить индекс первого появления x * /

    i = first(arr, 0, n-1, x, n);

      

    / * Если x не существует в arr [], вернуть -1 * /

    if(i == -1)

        return i;

          

    / * В противном случае получить индекс последнего вхождения x.

        Обратите внимание, что мы смотрим только в

        подмассив после первого появления * /

    j = last(arr, i, n-1, x, n);     

          

    / * счетчик возврата * /

    return j-i+1;

    }

      

    / * если x присутствует в arr [], то возвращает

    индекс ПЕРВОГО появления x в arr [0..n-1],

    в противном случае возвращает -1 * /

    static int first(int []arr, int low, int high, 

                                     int x, int n)

    {

    if(high >= low)

    {

        / * низкий + (высокий - низкий) / 2; * /

        int mid = (low + high)/2; 

        if( ( mid == 0 || x > arr[mid-1]) 

                            && arr[mid] == x)

        return mid;

        else if(x > arr[mid])

        return first(arr, (mid + 1), high, x, n);

        else

        return first(arr, low, (mid -1), x, n);

    }

    return -1;

    }

      

    / * если x присутствует в arr [], то возвращает

    индекс LAST появления x в arr [0..n-1],

    в противном случае возвращает -1 * /

    static int last(int []arr, int low,

                        int high, int x, int n)

    {

    if(high >= low)

    {

        / * низкий + (высокий - низкий) / 2; * /    

        int mid = (low + high)/2; 

        if( ( mid == n-1 || x < arr[mid+1])

                            && arr[mid] == x )

        return mid;

        else if(x < arr[mid])

        return last(arr, low, (mid -1), x, n);

        else

        return last(arr, (mid + 1), high, x, n);     

    }

    return -1;

    }

      

    public static void Main()

    {

        int []arr = {1, 2, 2, 3, 3, 3, 3};

          

        // Элемент для подсчета в arr []

        int x = 3; 

        int n = arr.Length;

        int c = count(arr, x, n);

          

        Console.Write(x + " occurs " + c + " times");

    }

}
// Этот код предоставлен Sam007


Выход:

3 occurs 4 times

Сложность времени: O (Logn)
Парадигма программирования: разделяй и властвуй

Пожалуйста, напишите комментарии, если вы обнаружите, что приведенные выше коды / алгоритмы неверны, или найдете другие способы решения той же проблемы.

Рекомендуемые посты:

Подсчет количества вхождений (или частоты) в отсортированном массиве

0.00 (0%) 0 votes