Dada una array no ordenada, cuente todos los elementos distintos en ella.
Ejemplos:
Input : arr[] = {10, 20, 20, 10, 30, 10}
Output : 3
There are three distinct elements 10, 20 and 30.
Input : arr[] = {10, 20, 20, 10, 20}
Output : 2
Una solución simple es ejecutar dos bucles. Para cada elemento, compruebe si ha aparecido antes. En caso afirmativo, incremente el recuento de elementos distintos.
C++
// C++ program to count distinct elements
// in a given array
#include <iostream>
using namespace std;
int countDistinct(int arr[], int n)
{
int res = 1;
// Pick all elements one by one
for (int i = 1; i < n; i++) {
int j = 0;
for (j = 0; j < i; j++)
if (arr[i] == arr[j])
break;
// If not printed earlier, then print it
if (i == j)
res++;
}
return res;
}
// Driver program to test above function
int main()
{
int arr[] = { 12, 10, 9, 45, 2, 10, 10, 45 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << countDistinct(arr, n);
return 0;
}
Java
// Java program to count distinct
// elements in a given array
class GFG
{
static int countDistinct(int arr[], int n)
{
int res = 1;
// Pick all elements one by one
for (int i = 1; i < n; i++)
{
int j = 0;
for (j = 0; j < i; j++)
if (arr[i] == arr[j])
break;
// If not printed earlier,
// then print it
if (i == j)
res++;
}
return res;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 12, 10, 9, 45, 2, 10, 10, 45 };
int n = arr.length;
System.out.println(countDistinct(arr, n));
}
}
// This code is contributed by Code_Mech.
Python3
# Python3 program to count distinct # elements in a given array def countDistinct(arr, n): res = 1 # Pick all elements one by one for i in range(1, n): j = 0 for j in range(i): if (arr[i] == arr[j]): break # If not printed earlier, then print it if (i == j + 1): res += 1 return res # Driver Code arr = [12, 10, 9, 45, 2, 10, 10, 45] n = len(arr) print(countDistinct(arr, n)) # This code is contributed by Mohit Kumar
C#
// C# program to count distinct
// elements in a given array
using System;
class GFG
{
static int countDistinct(int []arr, int n)
{
int res = 1;
// Pick all elements one by one
for (int i = 1; i < n; i++)
{
int j = 0;
for (j = 0; j < i; j++)
if (arr[i] == arr[j])
break;
// If not printed earlier,
// then print it
if (i == j)
res++;
}
return res;
}
// Driver code
public static void Main()
{
int []arr = { 12, 10, 9, 45,
2, 10, 10, 45 };
int n = arr.Length;
Console.WriteLine(countDistinct(arr, n));
}
}
// This code is contributed
// by Akanksha Rai
PHP
<?php
// PHP program to count distinct elements
// in a given array
function countDistinct( &$arr, $n)
{
$res = 1;
// Pick all elements one by one
for ( $i = 1; $i < $n; $i++)
{
for ($j = 0; $j < $i; $j++)
if ($arr[$i] == $arr[$j])
break;
// If not printed earlier,
// then print it
if ($i == $j)
$res++;
}
return $res;
}
// Driver Code
$arr = array( 12, 10, 9, 45, 2, 10, 10, 45 );
$n = count($arr);
echo countDistinct($arr, $n);
// This code is contributed by
// Rajput-Ji
?>
Javascript
<script>
// JavaScript program to count distinct elements
// in a given array
function countDistinct(arr, n)
{
let res = 1;
// Pick all elements one by one
for (let i = 1; i < n; i++) {
let j = 0;
for (j = 0; j < i; j++)
if (arr[i] === arr[j])
break;
// If not printed earlier, then print it
if (i === j)
res++;
}
return res;
}
// Driver program to test above function
let arr = [ 12, 10, 9, 45, 2, 10, 10, 45 ];
let n = arr.length;
document.write(countDistinct(arr, n));
// This code is contributed by Surbhi Tyagi
</script>
Producción
5
La complejidad temporal de la solución anterior es O(n 2 ). Podemos usar la clasificación para resolver el problema en tiempo O (nLogn). La idea es simple, primero ordene la array para que todas las ocurrencias de cada elemento sean consecutivas. Una vez que las ocurrencias se vuelven consecutivas, podemos atravesar la array ordenada y contar elementos distintos en tiempo O(n). A continuación se muestra la implementación de la idea.
C++
// C++ program to count all distinct elements
// in a given array
#include <algorithm>
#include <iostream>
using namespace std;
int countDistinct(int arr[], int n)
{
// First sort the array so that all
// occurrences become consecutive
sort(arr, arr + n);
// Traverse the sorted array
int res = 0;
for (int i = 0; i < n; i++) {
// Move the index ahead while
// there are duplicates
while (i < n - 1 && arr[i] == arr[i + 1])
i++;
res++;
}
return res;
}
// Driver program to test above function
int main()
{
int arr[] = { 6, 10, 5, 4, 9, 120, 4, 6, 10 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << countDistinct(arr, n);
return 0;
}
Java
// Java program to count all distinct elements
// in a given array
import java.util.Arrays;
class GFG
{
static int countDistinct(int arr[], int n)
{
// First sort the array so that all
// occurrences become consecutive
Arrays.sort(arr);
// Traverse the sorted array
int res = 0;
for (int i = 0; i < n; i++)
{
// Move the index ahead while
// there are duplicates
while (i < n - 1 &&
arr[i] == arr[i + 1])
{
i++;
}
res++;
}
return res;
}
// Driver code
public static void main(String[] args)
{
int arr[] = {6, 10, 5, 4, 9, 120, 4, 6, 10};
int n = arr.length;
System.out.println(countDistinct(arr, n));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to count all distinct # elements in a given array def countDistinct(arr, n): # First sort the array so that all # occurrences become consecutive arr.sort(); # Traverse the sorted array res = 0; i = 0; while(i < n): # Move the index ahead while # there are duplicates while (i < n - 1 and arr[i] == arr[i + 1]): i += 1; res += 1; i += 1; return res; # Driver Code arr = [ 6, 10, 5, 4, 9, 120, 4, 6, 10 ]; n = len(arr); print(countDistinct(arr, n)); # This code is contributed by mits
C#
// C# program to count all distinct elements
// in a given array
using System;
class GFG
{
static int countDistinct(int[] arr, int n)
{
// First sort the array so that all
// occurrences become consecutive
Array.Sort(arr);
// Traverse the sorted array
int res = 0;
for (int i = 0; i < n; i++)
{
// Move the index ahead while
// there are duplicates
while (i < n - 1 &&
arr[i] == arr[i + 1])
{
i++;
}
res++;
}
return res;
}
// Driver code
public static void Main()
{
int[] arr = {6, 10, 5, 4, 9, 120, 4, 6, 10};
int n = arr.Length;
Console.WriteLine(countDistinct(arr, n));
}
}
// This code is contributed by Code_Mech.
PHP
<?php
// PHP program to count all distinct
// elements in a given array
function countDistinct($arr, $n)
{
// First sort the array so that all
// occurrences become consecutive
sort($arr, 0);
// Traverse the sorted array
$res = 0;
for ($i = 0; $i < $n; $i++)
{
// Move the index ahead while
// there are duplicates
while ($i < $n - 1 &&
$arr[$i] == $arr[$i + 1])
$i++;
$res++;
}
return $res;
}
// Driver Code
$arr = array( 6, 10, 5, 4, 9, 120, 4, 6, 10 );
$n = sizeof($arr);
echo countDistinct($arr, $n);
// This code is contributed by Akanksha Rai
?>
Javascript
<script>
// JavaScript program to count all distinct elements
// in a given array
function countDistinct(arr,n)
{
// First sort the array so that all
// occurrences become consecutive
arr.sort(function(a,b){return a-b;});
// Traverse the sorted array
let res = 0;
for (let i = 0; i < n; i++)
{
// Move the index ahead while
// there are duplicates
while (i < n - 1 &&
arr[i] == arr[i + 1])
{
i++;
}
res++;
}
return res;
}
// Driver code
let arr=[6, 10, 5, 4, 9, 120, 4, 6, 10];
let n = arr.length;
document.write(countDistinct(arr, n));
// This code is contributed by unknown2108
</script>
Producción
6
Podemos usar Hashing para resolver esto en tiempo O(n) en promedio. La idea es recorrer la array dada de izquierda a derecha y realizar un seguimiento de los elementos visitados en un conjunto hash, ya que un conjunto consta solo de elementos únicos.
A continuación se muestra la implementación de la idea.
C++
/* CPP program to print all distinct elements
of a given array */
#include <bits/stdc++.h>
using namespace std;
// This function prints all distinct elements
int countDistinct(int arr[], int n)
{
// Creates an empty hashset
unordered_set<int> s;
// Traverse the input array
int res = 0;
for (int i = 0; i < n; i++) {
// If not present, then put it in
// hashtable and increment result
if (s.find(arr[i]) == s.end()) {
s.insert(arr[i]);
res++;
}
}
return res;
}
// Driver program to test above function
int main()
{
int arr[] = { 6, 10, 5, 4, 9, 120, 4, 6, 10 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << countDistinct(arr, n);
return 0;
}
Java
// Java Program to count
// Unique elements in Array
import java.util.*;
class GFG
{
// This method returns count
// of Unique elements
public static int countDistinct(int arr[],int n)
{
HashSet<Integer> hs = new HashSet<Integer>();
for(int i = 0; i < n; i++)
{
// add all the elements to the HashSet
hs.add(arr[i]);
}
// return the size of hashset as
// it consists of all Unique elements
return hs.size();
}
// Driver code
public static void main(String[] args)
{
int arr[] = new int[]{6, 10, 5, 4, 9,
120, 4, 6, 10};
System.out.println(countDistinct(arr,
arr.length));
}
}
// This code is contributed by Adarsh_Verma
Python3
''' Python3 program to print all distinct elements of a given array ''' # This function prints all distinct elements def countDistinct(arr, n): # Creates an empty hashset s = set() # Traverse the input array res = 0 for i in range(n): # If not present, then put it in # hashtable and increment result if (arr[i] not in s): s.add(arr[i]) res += 1 return res # Driver code arr = [6, 10, 5, 4, 9, 120, 4, 6, 10] n = len(arr) print(countDistinct(arr, n)) # This code is contributed by SHUBHAMSINGH10
C#
// C# Program to count
// Unique elements in Array
using System;
using System.Collections.Generic;
class GFG
{
// This method returns count
// of Unique elements
public static int countDistinct(int []arr,int n)
{
HashSet<int> hs = new HashSet<int>();
for(int i = 0; i < n; i++)
{
// add all the elements to the HashSet
hs.Add(arr[i]);
}
// return the size of hashset as
// it consists of all Unique elements
return hs.Count;
}
// Driver code
public static void Main()
{
int []arr = new int[]{6, 10, 5, 4, 9,
120, 4, 6, 10};
Console.WriteLine(countDistinct(arr,
arr.Length));
}
}
/* This code contributed by PrinciRaj1992 */
PHP
<?php
// PHP program to print all distinct elements
// of a given array
// This function prints all distinct elements
function countDistinct($arr, $n)
{
// Creates an empty hashset
$s = array();
// Traverse the input array
$res = 0;
for ($i = 0; $i < $n; $i++)
{
// If not present, then put it in
// hashtable and increment result
array_push($s,$arr[$i]);
}
$s = array_unique($s);
return count($s);
}
// Driver Code
$arr = array( 6, 10, 5, 4, 9, 120, 4, 6, 10 );
$n = count($arr);
echo countDistinct($arr, $n);
// This code is contributed by mits
?>
Javascript
<script>
// Javascript Program to count
// Unique elements in Array
// This method returns count
// of Unique elements
function countDistinct(arr,n)
{
let hs = new Set();
for(let i = 0; i < n; i++)
{
// add all the elements to the HashSet
hs.add(arr[i]);
}
// return the size of hashset as
// it consists of all Unique elements
return hs.size;
}
// Driver code
let arr=[6, 10, 5, 4, 9,120, 4, 6, 10];
document.write(countDistinct(arr,arr.length));
// This code is contributed by patel2127
</script>
Producción
6
Complejidad temporal: O(n)
Espacio Auxiliar: O(n)
Establecer enfoque STL:
Los conjuntos son un tipo de contenedores asociativos en los que cada elemento tiene que ser único, porque el valor del elemento lo identifica. El valor del elemento no se puede modificar una vez que se agrega al conjunto, aunque es posible eliminar y agregar el valor modificado de ese elemento. Aprovechamos la propiedad muy básica del conjunto STL de que almacena solo números únicos.
Ejemplos:
Arr = [1,2,2,2,3,16,2,8,2,1,8]
Distintos elementos presentes = [1,2,3,16,8]
El número total de elementos distintos en la array es 5
Algoritmo:
1. Inserte todos los elementos en el conjunto S uno por uno.
2. Almacene el tamaño total s del conjunto usando set::size() .
3.El tamaño total s es el número de elementos distintos presentes en la array.
C++
#include <bits/stdc++.h>
using namespace std;
// function that accepts the array and it's size and returns
// the number of distince elements
int distinct(int* arr, int len)
{
set<int> S; // declaring a set container using STL
for (int i = 0; i < len; i++) {
S.insert(arr[i]); // inserting all elements of the
// array into set
}
int ans = S.size(); // calculating the size of the set
return ans;
}
int main()
{
int arr[] = { 12, 10, 9, 45, 2, 10, 10, 45};
int l = sizeof(arr)
/ sizeof(
int); // calculating the size of the array
int dis_elements
= distinct(arr, l); // calling the function on array
cout << dis_elements << endl;
return 0;
}
Java
import java.util.*;
class GFG
{
// function that accepts the array and it's size and returns
// the number of distince elements
static int distinct(int[] arr, int len)
{
HashSet<Integer> S = new HashSet<>(); // declaring a set container using STL
for (int i = 0; i < len; i++) {
S.add(arr[i]); // inserting all elements of the
// array into set
}
int ans = S.size(); // calculating the size of the set
return ans;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 12, 10, 9, 45, 2, 10, 10, 45};
int l = arr.length; // calculating the size of the array
int dis_elements
= distinct(arr, l); // calling the function on array
System.out.print(dis_elements +"\n");
}
}
// This code is contributed by Rajput-Ji
Python3
# function that accepts the array and it's size and returns # the number of distince elements def distinct(arr, l): S = set(); # declaring a set container using STL for i in range(l): S.add(arr[i]); # inserting all elements of the # array into set ans = len(S); # calculating the size of the set return ans; # Driver code if __name__ == '__main__': arr = [ 12, 10, 9, 45, 2, 10, 10, 45] ; l = len(arr); # calculating the size of the array dis_elements = distinct(arr, l); # calling the function on array print(dis_elements , ""); # This code is contributed by Rajput-Ji
C#
using System;
using System.Collections.Generic;
public class GFG
{
// function that accepts the array and it's size and returns
// the number of distince elements
static int distinct(int[] arr, int len)
{
HashSet<int> S = new HashSet<int>(); // declaring a set container using STL
for (int i = 0; i < len; i++)
{
S.Add(arr[i]); // inserting all elements of the
// array into set
}
int ans = S.Count; // calculating the size of the set
return ans;
}
// Driver code
public static void Main(String[] args)
{
int []arr = { 12, 10, 9, 45, 2, 10, 10, 45 };
// calculating the size of the array
int l = arr.Length;
// calling the function on array
int dis_elements = distinct(arr, l);
Console.Write(dis_elements + "\n");
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// function that accepts the array and it's size and returns
// the number of distince elements
function distinct(arr , len)
{
var S = new Set(); // declaring a set container using STL
var i =0;
for (i = 0; i < len; i++)
{
S.add(arr[i]); // inserting all elements of the
// array into set
}
var ans = S.size; // calculating the size of the set
return ans;
}
// Driver code
var arr = [ 12, 10, 9, 45, 2, 10, 10, 45 ];
var l = arr.length; // calculating the size of the array
var dis_elements = distinct(arr, l); // calling the function on array
document.write(dis_elements);
// This code is contributed by Rajput-Ji.
</script>
Producción
5
Complejidad de tiempo: O(n*log(n))
Espacio auxiliar: O(n)