Dada una array ordenada arr[] de tamaño N , la tarea es encontrar el número de elementos únicos en esta array.
Nota: la array es muy grande y los números únicos son significativamente menores. es decir, (elementos únicos <<tamaño de la array).
Ejemplos:
Entrada: arr[] = {1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 5, 5, 7, 7, 8, 8, 9, 9, 10, 11, 12 }
Salida: 10
Explicación: 10 elementos únicos son: 1, 2, 3, 5, 7, 8, 9, 10, 11, 12Entrada: arr[] = {1, 1, 1, 2, 2, 2, 2, 3, 3, 4, 4, 5, 5, 5, 5, 9, 9, 9, 10, 10, 10}
Salida : 7
Explicación: 7 elementos únicos son: 1, 2, 3, 4, 5, 9, 10
Enfoque ingenuo: a medida que se ordena la array dada, uno de los enfoques simples atravesará todo el elemento y los comparará con los anteriores. Si es diferente, entonces cuente ese elemento.
Complejidad Temporal: O(N)
Espacio Auxiliar: O(1).
Enfoque basado en la búsqueda binaria: la idea es utilizar la búsqueda binaria porque la array está ordenada. Siga los pasos que se mencionan a continuación:
- Tome el primer número, luego encuentre su última ocurrencia o límite superior usando la búsqueda binaria.
- Luego cuéntalo como un elemento único.
- Coloque el puntero en el siguiente elemento diferente y repita el mismo paso.
Nota: Este algoritmo solo es efectivo cuando hay muy pocos elementos únicos.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code to implement above approach
#include <bits/stdc++.h>
using namespace std;
// Binary search to find the last occurrence
int nextIndex(int arr[], int N, int l,
int target)
{
int result = -1;
int r = N - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (arr[mid] == target) {
result = mid;
l = mid + 1;
}
else if (arr[mid] > target)
r = mid - 1;
else
l = mid + 1;
}
// Result will give the last occurrence &
// adding one will return next element
return result + 1;
}
// Function to find the number
// of unique elements
int unique(int arr[], int N)
{
int i = 0;
int count = 0;
while (i < N) {
// Returns the next element
i = nextIndex(arr, N, i, arr[i]);
count++;
}
return count;
}
// Driver Code
int main()
{
int arr[] = { 1, 1, 1, 1, 1, 1, 2, 2, 2,
2, 3, 5, 5, 7, 7, 8, 8, 9,
9, 10, 11, 12 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << unique(arr, N);
return 0;
}
Java
// Java code to implement above approach
class GFG {
// Binary search to find the last occurrence
static int nextIndex(int arr[], int N, int l, int target) {
int result = -1;
int r = N - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (arr[mid] == target) {
result = mid;
l = mid + 1;
} else if (arr[mid] > target)
r = mid - 1;
else
l = mid + 1;
}
// Result will give the last occurrence &
// adding one will return next element
return result + 1;
}
// Function to find the number
// of unique elements
static int unique(int arr[], int N) {
int i = 0;
int count = 0;
while (i < N) {
// Returns the next element
i = nextIndex(arr, N, i, arr[i]);
count++;
}
return count;
}
// Driver Code
public static void main(String args[]) {
int arr[] = { 1, 1, 1, 1, 1, 1, 2, 2, 2,
2, 3, 5, 5, 7, 7, 8, 8, 9,
9, 10, 11, 12 };
int N = arr.length;
System.out.println(unique(arr, N));
}
}
Python3
# Python code for the above approach # Binary search to find the last occurrence def nextIndex(arr, N, l, target): result = -1 r = N - 1 while (l <= r): mid = l + (r - l) // 2 if (arr[mid] == target): result = mid l = mid + 1 elif (arr[mid] > target): r = mid - 1 else: l = mid + 1 # Result will give the last occurrence & # adding one will return next element return result + 1 # Function to find the number # of unique elements def unique(arr, N): i = 0 count = 0 while (i < N): # Returns the next element i = nextIndex(arr, N, i, arr[i]) count += 1 return count # Driver Code arr = [1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 5, 5, 7, 7, 8, 8, 9, 9, 10, 11, 12] N = len(arr) print(unique(arr, N)) # This code is contributed by gfgking
C#
// C# program for above approach
using System;
using System.Collections.Generic;
public class GFG
{
// Binary search to find the last occurrence
static int nextIndex(int[] arr, int N, int l, int target) {
int result = -1;
int r = N - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (arr[mid] == target) {
result = mid;
l = mid + 1;
} else if (arr[mid] > target)
r = mid - 1;
else
l = mid + 1;
}
// Result will give the last occurrence &
// adding one will return next element
return result + 1;
}
// Function to find the number
// of unique elements
static int unique(int[] arr, int N) {
int i = 0;
int count = 0;
while (i < N) {
// Returns the next element
i = nextIndex(arr, N, i, arr[i]);
count++;
}
return count;
}
// Driver Code
static public void Main (){
int[] arr = { 1, 1, 1, 1, 1, 1, 2, 2, 2,
2, 3, 5, 5, 7, 7, 8, 8, 9,
9, 10, 11, 12 };
int N = arr.Length;
Console.WriteLine(unique(arr, N));
}
}
// This code is contributed by hrithikgarg03188
Javascript
<script>
// JavaScript code for the above approach
// Binary search to find the last occurrence
function nextIndex(arr, N, l,
target) {
let result = -1;
let r = N - 1;
while (l <= r) {
let mid = l + Math.floor((r - l) / 2);
if (arr[mid] == target) {
result = mid;
l = mid + 1;
}
else if (arr[mid] > target)
r = mid - 1;
else
l = mid + 1;
}
// Result will give the last occurrence &
// adding one will return next element
return result + 1;
}
// Function to find the number
// of unique elements
function unique(arr, N) {
let i = 0;
let count = 0;
while (i < N) {
// Returns the next element
i = nextIndex(arr, N, i, arr[i]);
count++;
}
return count;
}
// Driver Code
let arr = [1, 1, 1, 1, 1, 1, 2, 2, 2,
2, 3, 5, 5, 7, 7, 8, 8, 9,
9, 10, 11, 12];
let N = arr.length;
document.write(unique(arr, N));
// This code is contributed by Potta Lokesh
</script>
Producción
10
Complejidad temporal: K * logO(N). donde K = no. de elementos únicos.
Espacio Auxiliar: O(1).
Enfoque basado en divide y vencerás: este problema se puede resolver usando divide y vencerás . Idea es:
- Como los elementos duplicados son grandes, mire el primer y el último elemento de esta array ordenada.
- Si ambos son iguales, significa que solo este elemento está presente en toda la array y se contará como uno.
- Si son diferentes, divida la array en dos mitades y repita el paso anterior para cada array.
- El recuento final es el número de elementos únicos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to implement the above approach
#include <bits/stdc++.h>
using namespace std;
// Variable to store the number
// of unique elements
int cnt = 0;
// Function to find the number
// of unique elements
void UniqueElements(int arr[], int s,
int e, bool isDuplicate)
{
// Both start and end are same
if (arr[s] == arr[e]) {
// If the element is duplicate
if (isDuplicate == false) {
cnt++;
}
}
else {
int mid = s + (e - s) / 2;
UniqueElements(arr, s, mid, isDuplicate);
UniqueElements(arr, mid + 1, e,
arr[mid] == arr[mid + 1]);
}
}
// Function to count the number
// of unique elements
int unique(int arr[], int N)
{
UniqueElements(arr, 0, N - 1, 0);
return cnt;
}
// Driver Code
int main()
{
int arr[] = { 1, 1, 1, 1, 1, 1, 2, 2, 2,
2, 3, 5, 5, 7, 7, 8, 8, 9,
9, 10, 11, 12 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << unique(arr, N);
return 0;
}
Java
// Java code to implement the above approach
import java.util.*;
class GFG{
// Variable to store the number
// of unique elements
static int cnt = 0;
// Function to find the number
// of unique elements
static void UniqueElements(int arr[], int s,
int e, boolean isDuplicate)
{
// Both start and end are same
if (arr[s] == arr[e]) {
// If the element is duplicate
if (isDuplicate == false) {
cnt++;
}
}
else {
int mid = s + (e - s) / 2;
UniqueElements(arr, s, mid, isDuplicate);
UniqueElements(arr, mid + 1, e,
arr[mid] == arr[mid + 1]);
}
}
// Function to count the number
// of unique elements
static int unique(int arr[], int N)
{
UniqueElements(arr, 0, N - 1, false);
return cnt;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 1, 1, 1, 1, 1, 1, 2, 2, 2,
2, 3, 5, 5, 7, 7, 8, 8, 9,
9, 10, 11, 12 };
int N = arr.length;
System.out.print(unique(arr, N));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python code to implement the above approach # Variable to store the number # of unique elements cnt = 0; # Function to find the number # of unique elements def UniqueElements(arr, s, e, isDuplicate): global cnt # Both start and end are same if (arr[s] == arr[e]): # If the element is duplicate if (isDuplicate == False): cnt += 1; else: mid = s + (e - s) // 2; UniqueElements(arr, s, mid, isDuplicate); UniqueElements(arr, mid + 1, e, arr[mid] == arr[mid + 1]); # Function to count the number # of unique elements def unique(arr, N): UniqueElements(arr, 0, N - 1, False); return cnt; # Driver Code if __name__ == '__main__': arr = [ 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 5, 5, 7, 7, 8, 8, 9, 9, 10, 11, 12 ]; N = len(arr); print(unique(arr, N)); # This code is contributed by Rajput-Ji
C#
// C# code to implement the above approach
using System;
public class GFG{
// Variable to store the number
// of unique elements
static int cnt = 0;
// Function to find the number
// of unique elements
static void UniqueElements(int []arr, int s,
int e, bool isDuplicate)
{
// Both start and end are same
if (arr[s] == arr[e]) {
// If the element is duplicate
if (isDuplicate == false) {
cnt++;
}
}
else {
int mid = s + (e - s) / 2;
UniqueElements(arr, s, mid, isDuplicate);
UniqueElements(arr, mid + 1, e,
arr[mid] == arr[mid + 1]);
}
}
// Function to count the number
// of unique elements
static int unique(int []arr, int N)
{
UniqueElements(arr, 0, N - 1, false);
return cnt;
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 1, 1, 1, 1, 1, 1, 2, 2, 2,
2, 3, 5, 5, 7, 7, 8, 8, 9,
9, 10, 11, 12 };
int N = arr.Length;
Console.Write(unique(arr, N));
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// javascript code to implement the above approach
// Variable to store the number
// of unique elements
var cnt = 0;
// Function to find the number
// of unique elements
function UniqueElements(arr , s,e, isDuplicate)
{
// Both start and end are same
if (arr[s] == arr[e]) {
// If the element is duplicate
if (isDuplicate == false) {
cnt++;
}
}
else {
var mid = s + parseInt((e - s) / 2);
UniqueElements(arr, s, mid, isDuplicate);
UniqueElements(arr, mid + 1, e,
arr[mid] == arr[mid + 1]);
}
}
// Function to count the number
// of unique elements
function unique(arr , N)
{
UniqueElements(arr, 0, N - 1, false);
return cnt;
}
// Driver Code
var arr = [ 1, 1, 1, 1, 1, 1, 2, 2, 2,
2, 3, 5, 5, 7, 7, 8, 8, 9,
9, 10, 11, 12 ];
var N = arr.length;
document.write(unique(arr, N));
// This code is contributed by shikhasingrajput
</script>
Producción
10
Complejidad de tiempo: O(log(N)) para el caso promedio. El peor de los casos será O(N).
Espacio Auxiliar: O(1)