Dada una array que contiene todos los elementos que ocurren k veces, pero uno solo ocurre una vez. Encuentra ese elemento único.
Ejemplos:
Entrada: arr[] = {6, 2, 5, 2, 2, 6, 6}
k = 3
Salida: 5
Explicación: Cada elemento aparece 3 veces, acepte 5.Entrada: arr[] = {2, 2, 2, 10, 2}
k = 4
Salida: 10
Explicación: Cada elemento aparece 4 veces, acepte 10.
Una solución simple es usar dos bucles anidados. El bucle exterior elige un elemento uno por uno comenzando desde el elemento más a la izquierda. El ciclo interno verifica si el elemento está presente k veces o no. Si está presente, ignora el elemento; de lo contrario, imprime el elemento.
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 ordenar la array para que todas las ocurrencias de cada elemento se vuelvan consecutivas. Una vez que las ocurrencias se vuelven consecutivas, podemos recorrer la array ordenada e imprimir el elemento único en tiempo O(n).
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 una tabla hash. Finalmente, imprima el elemento con cuenta 1.
La solución basada en hashing requiere O(n) espacio extra. Podemos usar AND bit a bit para encontrar el elemento único en tiempo O(n) y espacio extra constante.
- Cree una array count[] de tamaño igual al número de bits en representaciones binarias de números.
- Rellene la array de conteo de manera que count[i] almacene el conteo de elementos de la array con i-th bit establecido.
- Resultado del formulario utilizando la array de conteo. Ponemos 1 en una posición i en el resultado si count[i] no es múltiplo de k. De lo contrario ponemos 0.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to find unique element where
// every element appears k times except one
#include <bits/stdc++.h>
using namespace std;
int findUnique(unsigned int a[], int n, int k)
{
// Create a count array to store count of
// numbers that have a particular bit set.
// count[i] stores count of array elements
// with i-th bit set.
int INT_SIZE = 8 * sizeof(unsigned int);
int count[INT_SIZE];
memset(count, 0, sizeof(count));
// AND(bitwise) each element of the array
// with each set digit (one at a time)
// to get the count of set bits at each
// position
for (int i = 0; i < INT_SIZE; i++)
for (int j = 0; j < n; j++)
if ((a[j] & (1 << i)) != 0)
count[i] += 1;
// Now consider all bits whose count is
// not multiple of k to form the required
// number.
unsigned res = 0;
for (int i = 0; i < INT_SIZE; i++)
res += (count[i] % k) * (1 << i);
// Before returning the res we need
// to check the occurrence of that
// unique element and divide it
res = res / (n % k);
return res;
}
// Driver Code
int main()
{
unsigned int a[] = { 6, 2, 5, 2, 2, 6, 6 };
int n = sizeof(a) / sizeof(a[0]);
int k = 3;
cout << findUnique(a, n, k);
return 0;
}
Java
// Java program to find unique element where
// every element appears k times except one
class GFG {
static int findUnique(int a[], int n, int k)
{
// Create a count array to store count of
// numbers that have a particular bit set.
// count[i] stores count of array elements
// with i-th bit set.
byte sizeof_int = 4;
int INT_SIZE = 8 * sizeof_int;
int count[] = new int[INT_SIZE];
// AND(bitwise) each element of the array
// with each set digit (one at a time)
// to get the count of set bits at each
// position
for (int i = 0; i < INT_SIZE; i++)
for (int j = 0; j < n; j++)
if ((a[j] & (1 << i)) != 0)
count[i] += 1;
// Now consider all bits whose count is
// not multiple of k to form the required
// number.
int res = 0;
for (int i = 0; i < INT_SIZE; i++)
res += (count[i] % k) * (1 << i);
// Before returning the res we need
// to check the occurrence of that
// unique element and divide it
res = res / (n % k);
return res;
}
// Driver Code
public static void main(String[] args)
{
int a[] = { 6, 2, 5, 2, 2, 6, 6 };
int n = a.length;
int k = 3;
System.out.println(findUnique(a, n, k));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python 3 program to find unique element where # every element appears k times except one import sys def findUnique(a, n, k): # Create a count array to store count of # numbers that have a particular bit set. # count[i] stores count of array elements # with i-th bit set. INT_SIZE = 8 * sys.getsizeof(int) count = [0] * INT_SIZE # AND(bitwise) each element of the array # with each set digit (one at a time) # to get the count of set bits at each # position for i in range(INT_SIZE): for j in range(n): if ((a[j] & (1 << i)) != 0): count[i] += 1 # Now consider all bits whose count is # not multiple of k to form the required # number. res = 0 for i in range(INT_SIZE): res += (count[i] % k) * (1 << i) # Before returning the res we need # to check the occurrence of that # unique element and divide it res = res / (n % k) return res # Driver Code if __name__ == '__main__': a = [6, 2, 5, 2, 2, 6, 6] n = len(a) k = 3 print(findUnique(a, n, k)) # This code is contributed by # Surendra_Gangwar
C#
// C# program to find unique element where
// every element appears k times except one
using System;
class GFG {
static int findUnique(int[] a, int n, int k)
{
// Create a count array to store count of
// numbers that have a particular bit set.
// count[i] stores count of array elements
// with i-th bit set.
byte sizeof_int = 4;
int INT_SIZE = 8 * sizeof_int;
int[] count = new int[INT_SIZE];
// AND(bitwise) each element of the array
// with each set digit (one at a time)
// to get the count of set bits at each
// position
for (int i = 0; i < INT_SIZE; i++)
for (int j = 0; j < n; j++)
if ((a[j] & (1 << i)) != 0)
count[i] += 1;
// Now consider all bits whose count is
// not multiple of k to form the required
// number.
int res = 0;
for (int i = 0; i < INT_SIZE; i++)
res += (count[i] % k) * (1 << i);
// Before returning the res we need
// to check the occurrence of that
// unique element and divide it
res = res / (n % k);
return res;
}
// Driver Code
public static void Main(String[] args)
{
int[] a = { 6, 2, 5, 2, 2, 6, 6 };
int n = a.Length;
int k = 3;
Console.WriteLine(findUnique(a, n, k));
}
}
// This code is contributed by PrinciRaj1992
PHP
<?php
//PHP program to find unique element where
// every element appears k times except one
function findUnique($a, $n, $k)
{
// Create a count array to store count of
// numbers that have a particular bit set.
// count[i] stores count of array elements
// with i-th bit set.
$INT_SIZE = 8 * PHP_INT_SIZE;
$count = array();
for($i=0; $i< $INT_SIZE; $i++)
$count[$i] = 0;
// AND(bitwise) each element of the array
// with each set digit (one at a time)
// to get the count of set bits at each
// position
for ( $i = 0; $i < $INT_SIZE; $i++)
for ( $j = 0; $j < $n; $j++)
if (($a[$j] & (1 << $i)) != 0)
$count[$i] += 1;
// Now consider all bits whose count is
// not multiple of k to form the required
// number.
$res = 0;
for ($i = 0; $i < $INT_SIZE; $i++)
$res += ($count[$i] % $k) * (1 << $i);
// Before returning the res we need
// to check the occurrence of that
// unique element and divide it
$res = $res / ($n % $k);
return $res;
}
// Driver Code
$a = array( 6, 2, 5, 2, 2, 6, 6 );
$n = count($a);
$k = 3;
echo findUnique($a, $n, $k);
// This code is contributed by Rajput-Ji
?>
Javascript
<script>
// Javascript program to find unique element where
// every element appears k times except one
function findUnique(a, n, k)
{
// Create a count array to store count of
// numbers that have a particular bit set.
// count[i] stores count of array elements
// with i-th bit set.
let sizeof_let = 4;
let LET_SIZE = 8 * sizeof_let;
let count = Array.from({length: LET_SIZE}, (_, i) => 0);
// AND(bitwise) each element of the array
// with each set digit (one at a time)
// to get the count of set bits at each
// position
for (let i = 0; i < LET_SIZE; i++)
for (let j = 0; j < n; j++)
if ((a[j] & (1 << i)) != 0)
count[i] += 1;
// Now consider all bits whose count is
// not multiple of k to form the required
// number.
let res = 0;
for (let i = 0; i < LET_SIZE; i++)
res += (count[i] % k) * (1 << i);
// Before returning the res we need
// to check the occurrence of that
// unique element and divide it
res = res / (n % k);
return res;
}
// driver function
let a = [ 6, 2, 5, 2, 2, 6, 6 ];
let n = a.length;
let k = 3;
document.write(findUnique(a, n, k));
</script>
5
Complejidad temporal: O(n)
Espacio auxiliar: O(1)
Este artículo es una contribución de Dhiman Mayank . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
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