repetidos - llenar vector sin repetir numeros java
Encontrar elemento duplicado en matriz en el tiempo O(n) (20)
- ordenar la matriz O (n ln n)
usando el truco de la ventana deslizante para atravesar la matriz O (n)
El espacio es O (1)
Arrays.sort(input); for(int i = 0, j = 1; j < input.length ; j++, i++){ if( input[i] == input[j]){ System.out.println(input[i]); while(j < input.length && input[i] == input[j]) j++; i = j - 1; } }
Caso de prueba int [] {1, 2, 3, 7, 7, 8, 3, 5, 7, 1, 2, 7}
salida 1, 2, 3, 7
Me han hecho esta pregunta en una entrevista de trabajo y me he estado preguntando cuál es la respuesta correcta.
Tiene una matriz de números de 0 a n-1, se elimina uno de los números y se lo reemplaza con un número que ya está en la matriz que hace un duplicado de ese número. ¿Cómo podemos detectar este duplicado en el tiempo O (n) ?
Por ejemplo, una matriz de 1,2,3,4 se convertiría en 1,2,2,4 .
La solución fácil del tiempo O (n 2 ) es usar un ciclo anidado para buscar el duplicado de cada elemento.
// Esto es similar al enfoque HashSet pero usa solo una estructura de datos:
int[] a = { 1, 4, 6, 7, 4, 6, 5, 22, 33, 44, 11, 5 };
LinkedHashMap<Integer, Integer> map = new LinkedHashMap<Integer, Integer>();
for (int i : a) {
map.put(i, map.containsKey(i) ? (map.get(i)) + 1 : 1);
}
Set<Entry<Integer, Integer>> es = map.entrySet();
Iterator<Entry<Integer, Integer>> it = es.iterator();
while (it.hasNext()) {
Entry<Integer, Integer> e = it.next();
if (e.getValue() > 1) {
System.out.println("Dupe " + e.getKey());
}
}
@rici tiene razón sobre el uso de tiempo y espacio: "Esto se puede hacer en O (n) tiempo y en O (1) espacio".
Sin embargo, la pregunta se puede ampliar a un requisito más amplio: no es necesario que haya un solo número duplicado y que los números no sean consecutivos.
OJ lo pone de esta manera here : (nota 3 aparentemente puede ser reducido)
Dado un conjunto nums que contiene n + 1 enteros donde cada entero está entre 1 yn (inclusive), demuestre que debe existir al menos un número duplicado. Suponga que solo hay un número duplicado, encuentre el duplicado.
Nota:
- No debe modificar la matriz (suponga que la matriz es de solo lectura).
- Debe usar solo constante, O (1) espacio extra.
- La complejidad de su tiempo de ejecución debe ser menor que O (n2).
- Solo hay un número duplicado en la matriz, pero podría repetirse más de una vez.
La pregunta está muy bien explicada y respondida here por Keith Schwarz, utilizando el algoritmo de búsqueda de ciclos de Floyd :
El truco principal que necesitamos usar para resolver este problema es observar que, dado que tenemos una matriz de n elementos que van de 0 a n - 2, podemos pensar que la matriz define una función f del conjunto {0, 1, ..., n - 1} sobre sí mismo. Esta función está definida por f (i) = A [i]. Dada esta configuración, un valor duplicado corresponde a un par de índices i! = J tal que f (i) = f (j). Nuestro desafío, por lo tanto, es encontrar este par (i, j). Una vez que lo tengamos, podemos encontrar fácilmente el valor duplicado simplemente seleccionando f (i) = A [i].
Pero, ¿cómo vamos a encontrar este valor repetido? Resulta que este es un problema bien estudiado en ciencias de la computación llamado detección de ciclos. La forma general del problema es la siguiente. Nos da una función f. Defina la secuencia x_i como
x_0 = k (for some k)
x_1 = f(x_0)
x_2 = f(f(x_0))
...
x_{n+1} = f(x_n)
Suponiendo que f se asigna desde un dominio a sí mismo, esta función tendrá una de las tres formas. Primero, si el dominio es infinito, entonces la secuencia puede ser infinitamente larga y no repetitiva. Por ejemplo, la función f (n) = n + 1 en los enteros tiene esta propiedad: ningún número se duplicará alguna vez. En segundo lugar, la secuencia podría ser un ciclo cerrado, lo que significa que hay algo i de modo que x_0 = x_i. En este caso, la secuencia recorre un conjunto fijo de valores indefinidamente. Finalmente, la secuencia podría ser "en forma de rho". En este caso, la secuencia se ve más o menos así:
x_0 -> x_1 -> ... x_k -> x_{k+1} ... -> x_{k+j}
^ |
| |
+-----------------------+
Es decir, la secuencia comienza con una cadena de elementos que ingresa en un ciclo y luego gira indefinidamente. Denotaremos el primer elemento del ciclo que se alcanza en la secuencia la "entrada" del ciclo.
Una implementación de Python también se puede encontrar here :
def findDuplicate(self, nums):
# The "tortoise and hare" step. We start at the end of the array and try
# to find an intersection point in the cycle.
slow = 0
fast = 0
# Keep advancing ''slow'' by one step and ''fast'' by two steps until they
# meet inside the loop.
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
# Start up another pointer from the end of the array and march it forward
# until it hits the pointer inside the array.
finder = 0
while True:
slow = nums[slow]
finder = nums[finder]
# If the two hit, the intersection index is the duplicate element.
if slow == finder:
return slow
Atraviese la matriz y compruebe el signo de la array[abs(array[i])] , si es positivo, haga que sea negativo y si es negativo, imprímalo de la siguiente manera:
import static java.lang.Math.abs;
public class FindRepeatedNumber {
private static void findRepeatedNumber(int arr[]) {
int i;
for (i = 0; i < arr.length; i++) {
if (arr[abs(arr[i])] > 0)
arr[abs(arr[i])] = -arr[abs(arr[i])];
else {
System.out.print(abs(arr[i]) + ",");
}
}
}
public static void main(String[] args) {
int arr[] = { 4, 2, 4, 5, 2, 3, 1 };
findRepeatedNumber(arr);
}
}
Referencia: http://www.geeksforgeeks.org/find-duplicates-in-on-time-and-constant-extra-space/
Como se describe,
Tiene una matriz de números de 0 a n-1, se elimina uno de los números y se lo reemplaza con un número que ya está en la matriz que hace un duplicado de ese número.
Supongo que los elementos de la matriz están ordenados, excepto la entrada duplicada. Si este es el escenario, podemos lograr el objetivo fácilmente de la siguiente manera:
public static void main(String[] args) {
//int arr[] = { 0, 1, 2, 2, 3 };
int arr[] = { 1, 2, 3, 4, 3, 6 };
int len = arr.length;
int iMax = arr[0];
for (int i = 1; i < len; i++) {
iMax = Math.max(iMax, arr[i]);
if (arr[i] < iMax) {
System.out.println(arr[i]);
break;
}else if(arr[i+1] <= iMax) {
System.out.println(arr[i+1]);
break;
}
}
}
- O (n) tiempo y O (1) espacio, por favor comparte tus pensamientos.
Escanee la matriz 3 veces:
- XOR juntos todos los elementos de la matriz ->
AXOR juntos todos los números de 0 a N-1 ->BAhoraA XOR B = X XOR D, donde X es el elemento eliminado, y D es el elemento duplicado. - Elija cualquier bit distinto de cero en
A XOR BXOR juntos todos los elementos de la matriz donde se establece este bit ->A1. XOR juntos todos los números de 0 a N-1 donde este bit está configurado ->B1. Ahora bienA1 XOR B1 = XoA1 XOR B1 = D - Escanee la matriz una vez más e intente encontrar
A1 XOR B1. Si se encuentra, este es el elemento duplicado. Si no, el elemento duplicado esA XOR B XOR A1 XOR B1.
Esta es una solución alternativa en O(n) tiempo y O(1) espacio. Es similar al de rici''s . Me resulta un poco más fácil de entender pero, en la práctica, se desbordará más rápido.
Deje que X sea el número que falta y R el número repetido.
Podemos suponer que los números son de
[1..n], es decir, cero no aparece. De hecho, mientras recorremos la matriz, podemos probar si se encontró cero y regresar de inmediato si no es así.Ahora considera:
sum(A) = n (n + 1) / 2 - X + R product(A) = n! R / X
donde el product(A) es el producto de todos los elementos en A omitiendo el cero. Tenemos dos ecuaciones en dos incógnitas de las cuales X y R se pueden derivar algebraicamente.
Editar : por demanda popular, aquí hay un ejemplo resuelto:
Vamos a establecer:
S = sum(A) - n (n + 1) / 2
P = n! / product(A)
Entonces nuestras ecuaciones se vuelven:
R - X = S
X = R P
que se puede resolver a:
R = S / (1 - P)
X = P R = P S / (1 - P)
Ejemplo:
A = [0 1 2 2 4]
n = A.length - 1 = 4
S = (1 + 2 + 2 + 4) - 4 * 5 / 2 = -1
P = 4! / (1 * 2 * 2 * 4) = 3 / 2
R = -1 / (1 - 3/2) = -1 / -1/2 = 2
X = 3/2 * 2 = 3
Este programa se basa en c # y si desea hacer este programa usando otro lenguaje de programación primero tiene que cambiar una matriz en orden ascendente y comparar el primer elemento con el segundo elemento. Si es igual, se encontrará un número repetido. El programa es
int[] array=new int[]{1,2,3,4,5,6,7,8,9,4};
Array.Sort(array);
for(int a=0;a<array.Length-1;a++)
{
if(array[a]==array[a+1]
{
Console.WriteLine("This {0} element is repeated",array[a]);
}
}
Console.WriteLine("Not repeated number in array");
Esto se puede hacer en el tiempo O(n) y en el espacio O(1) .
(El algoritmo solo funciona porque los números son enteros consecutivos en un rango conocido):
En una sola pasada a través del vector, calcule la suma de todos los números y la suma de los cuadrados de todos los números.
Reste la suma de todos los números de N(N-1)/2 . Llamar a esto A
Reste la suma de los cuadrados de N(N-1)(2N-1)/6 . Divida esto por A Llamar al resultado B
El número que se eliminó es (B + A)/2 y el número con el que fue reemplazado es (B - A)/2 .
Ejemplo:
El vector es [0, 1, 1, 2, 3, 5] :
N = 6
La suma del vector es 0 + 1 + 1 + 2 + 3 + 5 = 12. N (N-1) / 2 es 15. A = 3.
La suma de los cuadrados es 0 + 1 + 1 + 4 + 9 + 25 = 40. N (N-1) (2N-1) / 6 es 55. B = (55 - 40) / A = 5.
El número que se eliminó es (5 + 3) / 2 = 4.
El número por el que fue reemplazado es (5 - 3) / 2 = 1.
Por qué funciona:
La suma del vector original
[0, ..., N-1]esN(N-1)/2. Supongamos que el valorase eliminó y se reemplazó porb. Ahora la suma del vector modificado seráN(N-1)/2 + b - a. Si restamos la suma del vector modificado deN(N-1)/2obtenemosa - b. EntoncesA = a - b.De manera similar, la suma de los cuadrados del vector original es
N(N-1)(2N-1)/6. La suma de los cuadrados del vector modificado esN(N-1)(2N-1)/6 + b 2 - a 2. Restar la suma de los cuadrados del vector modificado de la suma original daa 2 - b 2, que es el mismo que(a+b)(ab). Entonces, si lo dividimos pora - b(es decir,A), obtenemosB = a + b.Ahora
B + A = a + b + a - b = 2ayB - A = a + b - (a - b) = 2b.
Podemos hacer uso de hashMap de manera eficiente:
Integer[] a = {1,2,3,4,0,1,5,2,1,1,1,};
HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
for(int x : a)
{
if (map.containsKey(x)) map.put(x,map.get(x)+1);
else map.put(x,1);
}
Integer [] keys = map.keySet().toArray(new Integer[map.size()]);
for(int x : keys)
{
if(map.get(x)!=1)
{
System.out.println(x+" repeats : "+map.get(x));
}
}
Puede proceder de la siguiente manera:
- ordenar su matriz mediante el uso de un algoritmo de clasificación de tiempo lineal (por ejemplo, clasificación de conteo) - O (N)
- escanee el arreglo ordenado y deténgalo tan pronto como dos elementos consecutivos sean iguales - O (N)
Puedes hacerlo en O (N) tiempo sin ningún espacio extra. Así es como funciona el algoritmo:
Iterar a través de la matriz de la siguiente manera:
Para cada elemento encontrado, establezca su valor de índice correspondiente en negativo. Por ejemplo: si encuentra un [0] = 2. Llegó a un [2] y niega el valor.
Al hacer esto, lo indicas para ser encontrado. Como sabes que no puedes tener números negativos, también sabes que tú eres el que lo negó.
Comprueba si el índice correspondiente al valor ya está marcado como negativo, si es así obtienes el elemento duplicado. Por ejemplo: si a [0] = 2, vaya a a [2] y verifique si es negativo.
Digamos que tienes siguiente matriz:
int a[] = {2,1,2,3,4};
Después del primer elemento su matriz será:
int a[] = {2,1,-2,3,4};
Después del segundo elemento, su matriz será:
int a[] = {2,-1,-2,3,4};
Cuando alcanzas el tercer elemento, vas a un [2] y ves que ya es negativo. Obtienes el duplicado.
Sugiero usar un BitSet. Sabemos que N es lo suficientemente pequeño para la indexación de matriz, por lo que el BitSet será de un tamaño razonable.
Para cada elemento de la matriz, verifique el bit correspondiente a su valor. Si ya está configurado, ese es el duplicado. Si no, configure el bit.
Tenemos la matriz original int A[N]; Cree una segunda matriz bool B[N] también, de tipo bool=false . Itera el primer conjunto y establece B[A[i]]=true si fue falso, sino bing!
Una solución de trabajo:
número asume son enteros
crear una matriz de [0 .. N]
int[] counter = new int[N];
A continuación, iterar leer e incrementar el contador:
if (counter[val] >0) {
// duplicate
} else {
counter[val]++;
}
Usa hashtable Incluir un elemento en una tabla hash es O (1).
Use un HashSet para mantener todos los números ya vistos. Opera en tiempo (amortizado) O(1) , por lo que el total es O(N) .
public void duplicateNumberInArray {
int a[] = new int[10];
Scanner inp = new Scanner(System.in);
for(int i=1;i<=5;i++){
System.out.println("enter no. ");
a[i] = inp.nextInt();
}
Set<Integer> st = new HashSet<Integer>();
Set<Integer> s = new HashSet<Integer>();
for(int i=1;i<=5;i++){
if(!st.add(a[i])){
s.add(a[i]);
}
}
Iterator<Integer> itr = s.iterator();
System.out.println("Duplicate numbers are");
while(itr.hasNext()){
System.out.println(itr.next());
}
}
En primer lugar, crear una matriz de números enteros utilizando la clase de escáner. Luego iterando un ciclo a través de los números y verificando si se puede agregar el número al conjunto (los números se pueden agregar para establecer solo cuando ese número particular no debería estar ya establecido, significa que el conjunto no permite el número duplicado para agregar y devolver un booleano vale FALSE al agregar valor duplicado) .Si no. no se puede agregar significa que está duplicado, así que agrega ese número duplicado a otro conjunto para que podamos imprimir más tarde. Tenga en cuenta que estamos agregando el número duplicado en un conjunto porque es posible que el número duplicado se repita varias veces, por lo tanto, agréguelo solo una vez. Al último estamos imprimiendo el conjunto usando Iterator.
int a[] = {2,1,2,3,4};
int b[] = {0};
for(int i = 0; i < a.size; i++)
{
if(a[i] == a[i+1])
{
//duplicate found
//copy it to second array
b[i] = a[i];
}
}
public class FindDuplicate {
public static void main(String[] args) {
// assume the array is sorted, otherwise first we have to sort it.
// time efficiency is o(n)
int elementData[] = new int[] { 1, 2, 3, 3, 4, 5, 6, 8, 8 };
int count = 1;
int element1;
int element2;
for (int i = 0; i < elementData.length - 1; i++) {
element1 = elementData[i];
element2 = elementData[count];
count++;
if (element1 == element2) {
System.out.println(element2);
}
}
}
}