Dada una array ordenada arr[] y un número x, escriba una función que cuente las ocurrencias de x en arr[]. La complejidad de tiempo esperada es O (Inicio de sesión)
Ejemplos:
C++
// C++ program to count occurrences of an element
#include<bits/stdc++.h>
using namespace std;
// Returns number of times x occurs in 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;
}
// Driver code
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
// Java program to count occurrences
// of an element
class Main
{
// Returns number of times x occurs in 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 program to count # occurrences of an element # Returns number of times x # occurs in arr[0..n-1] def countOccurrences(arr, n, x): res = 0 for i in range(n): if x == arr[i]: res += 1 return res # Driver code arr = [1, 2, 2, 2, 2, 3, 4, 7 ,8 ,8] n = len(arr) x = 2 print (countOccurrences(arr, n, x))
C#
// C# program to count occurrences
// of an element
using System;
class GFG
{
// Returns number of times x
// occurs in 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;
}
// driver code
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));
}
}
// This code is contributed by Sam007
PHP
<?php
// PHP program to count occurrences
// of an element
// Returns number of times x
// occurs in arr[0..n-1]
function countOccurrences($arr, $n, $x)
{
$res = 0;
for ($i = 0; $i < $n; $i++)
if ($x == $arr[$i])
$res++;
return $res;
}
// Driver code
$arr = array(1, 2, 2, 2, 2, 3, 4, 7 ,8 ,8 );
$n = count($arr);
$x = 2;
echo countOccurrences($arr,$n, $x);
// This code is contributed by Sam007
?>
Javascript
<script>
// Javascript program to count occurrences
// of an element
// Returns number of times x occurs in arr[0..n-1]
function countOccurrences(arr,n,x)
{
let res = 0;
for (let i=0; i<n; i++)
{
if (x == arr[i])
res++;
}
return res;
}
arr=[1, 2, 2, 2, 2, 3, 4, 7 ,8 ,8]
let n = arr.length;
let x = 2;
document.write(countOccurrences(arr, n, x));
// This code is contributed by avanitrachhadiya2155
</script>
C++
// C++ program to count occurrences of an element
#include <bits/stdc++.h>
using namespace std;
// A recursive binary search function. It returns
// location of x in given array arr[l..r] is present,
// otherwise -1
int binarySearch(int arr[], int l, int r, int x)
{
if (r < l)
return -1;
int mid = l + (r - l) / 2;
// If the element is present at the middle
// itself
if (arr[mid] == x)
return mid;
// If element is smaller than mid, then
// it can only be present in left subarray
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
// Else the element can only be present
// in right subarray
return binarySearch(arr, mid + 1, r, x);
}
// Returns number of times x occurs in arr[0..n-1]
int countOccurrences(int arr[], int n, int x)
{
int ind = binarySearch(arr, 0, n - 1, x);
// If element is not present
if (ind == -1)
return 0;
// Count elements on left side.
int count = 1;
int left = ind - 1;
while (left >= 0 && arr[left] == x)
count++, left--;
// Count elements on right side.
int right = ind + 1;
while (right < n && arr[right] == x)
count++, right++;
return count;
}
// Driver code
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
// Java program to count
// occurrences of an element
class GFG
{
// A recursive binary search
// function. It returns location
// of x in given array arr[l..r]
// is present, otherwise -1
static int binarySearch(int arr[], int l,
int r, int x)
{
if (r < l)
return -1;
int mid = l + (r - l) / 2;
// If the element is present
// at the middle itself
if (arr[mid] == x)
return mid;
// If element is smaller than
// mid, then it can only be
// present in left subarray
if (arr[mid] > x)
return binarySearch(arr, l,
mid - 1, x);
// Else the element can
// only be present in
// right subarray
return binarySearch(arr, mid + 1, r, x);
}
// Returns number of times x
// occurs in arr[0..n-1]
static int countOccurrences(int arr[],
int n, int x)
{
int ind = binarySearch(arr, 0,
n - 1, x);
// If element is not present
if (ind == -1)
return 0;
// Count elements on left side.
int count = 1;
int left = ind - 1;
while (left >= 0 &&
arr[left] == x)
{
count++;
left--;
}
// Count elements
// on right side.
int right = ind + 1;
while (right < n &&
arr[right] == x)
{
count++;
right++;
}
return count;
}
// Driver code
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));
}
}
// This code is contributed
// by ChitraNayal
Python 3
# Python 3 program to count # occurrences of an element # A recursive binary search # function. It returns location # of x in given array arr[l..r] # is present, otherwise -1 def binarySearch(arr, l, r, x): if (r < l): return -1 mid = int( l + (r - l) / 2) # If the element is present # at the middle itself if arr[mid] == x: return mid # If element is smaller than # mid, then it can only be # present in left subarray if arr[mid] > x: return binarySearch(arr, l, mid - 1, x) # Else the element # can only be present # in right subarray return binarySearch(arr, mid + 1, r, x) # Returns number of times # x occurs in arr[0..n-1] def countOccurrences(arr, n, x): ind = binarySearch(arr, 0, n - 1, x) # If element is not present if ind == -1: return 0 # Count elements # on left side. count = 1 left = ind - 1 while (left >= 0 and arr[left] == x): count += 1 left -= 1 # Count elements on # right side. right = ind + 1; while (right < n and arr[right] == x): count += 1 right += 1 return count # Driver code arr = [ 1, 2, 2, 2, 2, 3, 4, 7, 8, 8 ] n = len(arr) x = 2 print(countOccurrences(arr, n, x)) # This code is contributed # by ChitraNayal
C#
// C# program to count
// occurrences of an element
using System;
class GFG
{
// A recursive binary search
// function. It returns location
// of x in given array arr[l..r]
// is present, otherwise -1
static int binarySearch(int[] arr, int l,
int r, int x)
{
if (r < l)
return -1;
int mid = l + (r - l) / 2;
// If the element is present
// at the middle itself
if (arr[mid] == x)
return mid;
// If element is smaller than
// mid, then it can only be
// present in left subarray
if (arr[mid] > x)
return binarySearch(arr, l,
mid - 1, x);
// Else the element
// can only be present
// in right subarray
return binarySearch(arr, mid + 1,
r, x);
}
// Returns number of times x
// occurs in arr[0..n-1]
static int countOccurrences(int[] arr,
int n, int x)
{
int ind = binarySearch(arr, 0,
n - 1, x);
// If element is not present
if (ind == -1)
return 0;
// Count elements on left side.
int count = 1;
int left = ind - 1;
while (left >= 0 &&
arr[left] == x)
{
count++;
left--;
}
// Count elements on right side.
int right = ind + 1;
while (right < n &&
arr[right] == x)
{
count++;
right++;
}
return count;
}
// Driver code
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));
}
}
// This code is contributed
// by ChitraNayal
PHP
<?php
// PHP program to count
// occurrences of an element
// A recursive binary search
// function. It returns location
// of x in given array arr[l..r]
// is present, otherwise -1
function binarySearch(&$arr, $l,
$r, $x)
{
if ($r < $l)
return -1;
$mid = $l + ($r - $l) / 2;
// If the element is present
// at the middle itself
if ($arr[$mid] == $x)
return $mid;
// If element is smaller than
// mid, then it can only be
// present in left subarray
if ($arr[$mid] > $x)
return binarySearch($arr, $l,
$mid - 1, $x);
// Else the element
// can only be present
// in right subarray
return binarySearch($arr, $mid + 1,
$r, $x);
}
// Returns number of times
// x occurs in arr[0..n-1]
function countOccurrences($arr, $n, $x)
{
$ind = binarySearch($arr, 0,
$n - 1, $x);
// If element is not present
if ($ind == -1)
return 0;
// Count elements
// on left side.
$count = 1;
$left = $ind - 1;
while ($left >= 0 &&
$arr[$left] == $x)
{
$count++;
$left--;
}
// Count elements on right side.
$right = $ind + 1;
while ($right < $n &&
$arr[$right] == $x)
{
$count++;
$right++;
}
return $count;
}
// Driver code
$arr = array( 1, 2, 2, 2, 2,
3, 4, 7, 8, 8 );
$n = sizeof($arr);
$x = 2;
echo countOccurrences($arr, $n, $x);
// This code is contributed
// by ChitraNayal
?>
Javascript
<script>
// Javascript program to count occurrences of an element
// A recursive binary search function. It returns
// location of x in given array arr[l..r] is present,
// otherwise -1
function binarySearch(arr, l, r, x)
{
if (r < l)
return -1;
var mid = l + parseInt((r - l) / 2);
// If the element is present at the middle
// itself
if (arr[mid] == x)
return mid;
// If element is smaller than mid, then
// it can only be present in left subarray
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
// Else the element can only be present
// in right subarray
return binarySearch(arr, mid + 1, r, x);
}
// Returns number of times x occurs in arr[0..n-1]
function countOccurrences(arr, n, x)
{
var ind = binarySearch(arr, 0, n - 1, x);
// If element is not present
if (ind == -1)
return 0;
// Count elements on left side.
var count = 1;
var left = ind - 1;
while (left >= 0 && arr[left] == x)
count++, left--;
// Count elements on right side.
var right = ind + 1;
while (right < n && arr[right] == x)
count++, right++;
return count;
}
// Driver code
var arr = [ 1, 2, 2, 2, 2, 3, 4, 7, 8, 8 ];
var n = arr.length;
var x = 2;
document.write(countOccurrences(arr, n, x));
// This code is contributed by noob2000.
</script>
C++
// C++ program to count occurrences of an element
// in a sorted array.
# include <bits/stdc++.h>
using namespace std;
/* if x is present in arr[] then returns the count
of occurrences of x, otherwise returns 0. */
int count(int arr[], int x, int n)
{
/* get the index of first occurrence of x */
int *low = lower_bound(arr, arr+n, x);
// If element is not present, return 0
if (low == (arr + n) || *low != x)
return 0;
/* Else get the index of last occurrence of x.
Note that we are only looking in the
subarray after first occurrence */
int *high = upper_bound(low, arr+n, x);
/* return count */
return high - low;
}
/* driver program to test above functions */
int main()
{
int arr[] = {1, 2, 2, 3, 3, 3, 3};
int x = 3; // Element to be counted in arr[]
int n = sizeof(arr)/sizeof(arr[0]);
int c = count(arr, x, n);
printf(" %d occurs %d times ", x, c);
return 0;
}
C
# include <stdio.h>
/* if x is present in arr[] then returns
the index of FIRST occurrence
of x in arr[0..n-1], otherwise returns -1 */
int first(int arr[], int low, int high, int x, int n)
{
if(high >= low)
{
int mid = (low + high)/2; /*low + (high - low)/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;
}
/* if x is present in arr[] then returns the
index of LAST occurrence of x in arr[0..n-1],
otherwise returns -1 */
int last(int arr[], int low, int high, int x, int n)
{
if (high >= low)
{
int mid = (low + high)/2; /*low + (high - low)/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;
}
/* if x is present in arr[] then returns the count
of occurrences of x, otherwise returns -1. */
int count(int arr[], int x, int n)
{
int i; // index of first occurrence of x in arr[0..n-1]
int j; // index of last occurrence of x in arr[0..n-1]
/* get the index of first occurrence of x */
i = first(arr, 0, n-1, x, n);
/* If x doesn't exist in arr[] then return -1 */
if(i == -1)
return i;
/* Else get the index of last occurrence of x.
Note that we are only looking in the subarray
after first occurrence */
j = last(arr, i, n-1, x, n);
/* return count */
return j-i+1;
}
/* driver program to test above functions */
int main()
{
int arr[] = {1, 2, 2, 3, 3, 3, 3};
int x = 3; // Element to be counted in 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
// Java program to count occurrences
// of an element
class Main
{
/* if x is present in arr[] then returns
the count of occurrences of x,
otherwise returns -1. */
static int count(int arr[], int x, int n)
{
// index of first occurrence of x in arr[0..n-1]
int i;
// index of last occurrence of x in arr[0..n-1]
int j;
/* get the index of first occurrence of x */
i = first(arr, 0, n-1, x, n);
/* If x doesn't exist in arr[] then return -1 */
if(i == -1)
return i;
/* Else get the index of last occurrence of x.
Note that we are only looking in the
subarray after first occurrence */
j = last(arr, i, n-1, x, n);
/* return count */
return j-i+1;
}
/* if x is present in arr[] then returns the
index of FIRST occurrence of x in arr[0..n-1],
otherwise returns -1 */
static int first(int arr[], int low, int high, int x, int n)
{
if(high >= low)
{
/*low + (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;
}
/* if x is present in arr[] then returns the
index of LAST occurrence of x in arr[0..n-1],
otherwise returns -1 */
static int last(int arr[], int low, int high, int x, int n)
{
if(high >= low)
{
/*low + (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};
// Element to be counted in arr[]
int x = 3;
int n = arr.length;
int c = count(arr, x, n);
System.out.println(x+" occurs "+c+" times");
}
}
Python3
# Python3 program to count
# occurrences of an element
# if x is present in arr[] then
# returns the count of occurrences
# of x, otherwise returns -1.
def count(arr, x, n):
# get the index of first
# occurrence of x
i = first(arr, 0, n-1, x, n)
# If x doesn't exist in
# arr[] then return -1
if i == -1:
return i
# Else get the index of last occurrence
# of x. Note that we are only looking
# in the subarray after first occurrence
j = last(arr, i, n-1, x, n);
# return count
return j-i+1;
# if x is present in arr[] then return
# the index of FIRST occurrence of x in
# arr[0..n-1], otherwise returns -1
def first(arr, low, high, x, n):
if high >= low:
# low + (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;
# if x is present in arr[] then return
# the index of LAST occurrence of x
# in arr[0..n-1], otherwise returns -1
def last(arr, low, high, x, n):
if high >= low:
# low + (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
# driver program to test above functions
arr = [1, 2, 2, 3, 3, 3, 3]
x = 3 # Element to be counted in arr[]
n = len(arr)
c = count(arr, x, n)
print ("%d occurs %d times "%(x, c))
C#
// C# program to count occurrences
// of an element
using System;
class GFG
{
/* if x is present in arr[] then returns
the count of occurrences of x,
otherwise returns -1. */
static int count(int []arr, int x, int n)
{
// index of first occurrence of x in arr[0..n-1]
int i;
// index of last occurrence of x in arr[0..n-1]
int j;
/* get the index of first occurrence of x */
i = first(arr, 0, n-1, x, n);
/* If x doesn't exist in arr[] then return -1 */
if(i == -1)
return i;
/* Else get the index of last occurrence of x.
Note that we are only looking in the
subarray after first occurrence */
j = last(arr, i, n-1, x, n);
/* return count */
return j-i+1;
}
/* if x is present in arr[] then returns the
index of FIRST occurrence of x in arr[0..n-1],
otherwise returns -1 */
static int first(int []arr, int low, int high,
int x, int n)
{
if(high >= low)
{
/*low + (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;
}
/* if x is present in arr[] then returns the
index of LAST occurrence of x in arr[0..n-1],
otherwise returns -1 */
static int last(int []arr, int low,
int high, int x, int n)
{
if(high >= low)
{
/*low + (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};
// Element to be counted in arr[]
int x = 3;
int n = arr.Length;
int c = count(arr, x, n);
Console.Write(x + " occurs " + c + " times");
}
}
// This code is contributed by Sam007
Javascript
<script>
// Javascript program to count occurrences
// of an element
/* if x is present in arr[] then returns
the count of occurrences of x,
otherwise returns -1. */
function count(arr, x, n)
{
// Index of first occurrence of x in arr[0..n-1]
let i;
// Index of last occurrence of x in arr[0..n-1]
let j;
// Get the index of first occurrence of x
i = first(arr, 0, n - 1, x, n);
// If x doesn't exist in arr[] then return -1
if (i == -1)
return i;
// Else get the index of last occurrence of x.
// Note that we are only looking in the
// subarray after first occurrence
j = last(arr, i, n - 1, x, n);
// return count
return j - i + 1;
}
// if x is present in arr[] then returns the
// index of FIRST occurrence of x in arr[0..n-1],
// otherwise returns -1
function first(arr, low, high, x, n)
{
if (high >= low)
{
// low + (high - low)/2;
let 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;
}
// If x is present in arr[] then returns the
// index of LAST occurrence of x in arr[0..n-1],
// otherwise returns -1
function last(arr, low, high, x, n)
{
if (high >= low)
{
/*low + (high - low)/2;*/
let mid = Math.floor((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;
}
// Driver code
let arr = [ 1, 2, 2, 3, 3, 3, 3 ];
// Element to be counted in arr[]
let x = 3;
let n = arr.length;
let c = count(arr, x, n);
document.write(x + " occurs " + c + " times");
// This code is contributed by target_2
</script>
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count occurrences
int countOccurrences(int arr[],
int x, int N)
{
int count = 0;
for (int i=0; i < N; i++)
if (arr[i] == x)
count++;
return count;
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 2, 2, 2, 3, 4, 7, 8, 8 };
int x = 2;
int N = sizeof(arr) / sizeof(arr[0]);
// displaying the frequency of x in ArrayList
cout <<x << " occurs "
<< countOccurrences(arr, x, N)
<< " times";
return 0;
}
// This code is contributed by code_hunt.
Java
/*package whatever //do not write package name here */
import java.util.ArrayList;
import java.util.Collections;
public class GFG {
// Function to count occurrences
static int countOccurrences(ArrayList<Integer> clist,
int x)
{
// returning the frequency of
// element x in the ArrayList
// using Collections.frequency() method
return Collections.frequency(clist, x);
}
// Driver Code
public static void main(String args[])
{
int arr[] = { 1, 2, 2, 2, 2, 3, 4, 7, 8, 8 };
int x = 2;
ArrayList<Integer> clist = new ArrayList<>();
// adding elements of array to
// ArrayList
for (int i : arr)
clist.add(i);
// displaying the frequency of x in ArrayList
System.out.println(x + " occurs "
+ countOccurrences(clist, x)
+ " times");
}
}
Python3
# Python code to implement the approach # Function to count occurrences def countOccurrences(arr, x) : count = 0 n = len(arr) for i in range(n) : if (arr[i] == x): count += 1 return count # Driver Code if __name__ == "__main__": arr = [ 1, 2, 2, 2, 2, 3, 4, 7, 8, 8 ] x = 2 # displaying the frequency of x in ArrayList print(x , "occurs" , countOccurrences(arr, x) , "times") # This code is contributed by sanjoy_62.
C#
// C# program for the above approach
using System;
public class GFG
{
// Function to count occurrences
static int countOccurrences(int[] arr,
int x)
{
int count = 0;
int n = arr.Length;
for (int i=0; i < n; i++)
if (arr[i] == x)
count++;
return count;
}
// Driver Code
public static void Main (string[] args)
{
int[] arr = { 1, 2, 2, 2, 2, 3, 4, 7, 8, 8 };
int x = 2;
// displaying the frequency of x in ArrayList
Console.WriteLine(x + " occurs "
+ countOccurrences(arr, x)
+ " times");
}
}
// This code is contributed by avijitmondal1998.
Javascript
<script>
// javascript program for above approach
// Function to count occurrences
function countOccurrences(arr, x)
{
let count = 0;
let n = arr.length;
for (let i=0; i < n; i++)
if (arr[i] == x)
count++;
return count;
}
// Driver Code
let arr = [ 1, 2, 2, 2, 2, 3, 4, 7, 8, 8 ];
let x = 2;
// displaying the frequency of x in ArrayList
document.write(x + " occurs "
+ countOccurrences(arr, x)
+ " times");
// This code is contributed by splevel62.
</script>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA