Reducir la cantidad de elementos distintos en el arreglo

06 Aug, 2023 Programación 0

Tengo una matriz de números y otro número K.

Mi tarea es reducir la cantidad de elementos distintos en la matriz. Para eso, puedo actualizar la matriz varias veces. Para actualizar la matriz, debo seguir estos pasos:

Seleccionar un elemento en el índice i y sumarle ese elemento K, y restar K a todos los demás elementos restantes.

Para actualizar una matriz, puedo seleccionar el mismo índice varias veces.

Ejemplo:

K = 1
Array: [3,1,3]    
Respuesta: 3

Estoy eligiendo el índice = 1, como [3-1, 1+1, 3-1] = [2,2,2] por lo que tenemos el número 2 que aparece 3 veces, por lo que este elemento ocurre el número máximo de veces. Por lo tanto, la respuesta es 3.

Otro ejemplo:

K = 1
Array: [1,2,2]
Respuesta: 2

No es posible hacer que todos los elementos sean iguales, por lo que tenemos el número 2 que aparece 2 veces, por lo que la respuesta es 2.

El tamaño de la matriz puede ser [1, 1000], y el valor de K y los elementos en la matriz están en el rango [0, 1000]

Aquí está mi código que intenté, pero mi enfoque no es correcto.

“`java
public static int process(int K, int[] A) {
Map<integer, integer=""> map = new TreeMap<>();
for (int key : A) {
map.put(key, map.getOrDefault(key, 0) + 1);
}
int result = 0;
boolean flag = false;
int last = -1, cur = -1;
for (int key : map.keySet()) {
if (flag == false) {
flag = true;
last = key;
continue;
}
cur = key;
int a = map.get(last), b = map.get(cur);
if (Math.abs(last – cur) > K) {
result += a + b;
} else {
result += Math.max(a, b);
}
}
last = cur;

<pre><code>return result;
</code></pre>

}
“`</integer,>

davy.ai

August 6, 2023 at 12:29 pm

El problema dado se puede resolver en una complejidad de tiempo O(n log n) utilizando una cola de prioridad. Aquí están los pasos:

Inicializar una cola de prioridad (montículo mínimo) con todos los elementos del arreglo dado.
Inicializar un mapa para almacenar la frecuencia de cada elemento en la cola de prioridad.
Inicializar una variable “count” para almacenar el recuento máximo de cualquier elemento (inicializado en 1).
Ahora, para cada elemento en la cola de prioridad, hacer lo siguiente:
a. Obtener el elemento con el valor mínimo (digamos x) de la cola de prioridad y eliminarlo.
b. Incrementar el recuento de x en el mapa.
c. Agregar K a x e insertarlo de nuevo en la cola de prioridad.
d. Decrementar todos los demás elementos en la cola de prioridad en K.
e. Si el nuevo elemento x después de la adición de K sigue siendo menor o igual al elemento mínimo en la cola de prioridad, entonces repetir los pasos a-e hasta que esta condición sea falsa.
f. Actualizar el recuento máximo “count”.
Devolver el recuento máximo “count” como respuesta.

Aquí está el código en Java que implementa el algoritmo anterior:

“`java
import java.util.*;

public class ReduceArrayDistinct {
public static int reduceDistinct(int K, int[] A) {
// Inicializar cola de prioridad con todos los elementos del arreglo
PriorityQueue pq = new PriorityQueue<>();
for (int x : A) {
pq.offer(x);
}

    // Inicializar mapa para almacenar la frecuencia de cada elemento en la cola de prioridad
    Map<integer, integer=""> map = new HashMap<>();
    for (int x : A) {
        map.put(x, map.getOrDefault(x, 0) + 1);
    }

    int count = 1; // Recuento máximo de cualquier elemento

    // Procesar cada elemento en la cola de prioridad
    while (!pq.isEmpty()) {
        int x = pq.poll(); // Obtener el elemento mínimo de la cola de prioridad
        int freq = map.get(x);
        count = Math.max(count, freq); // Actualizar recuento máximo

        int newX = x + K; // Agregar K a x

        // Decrementar todos los demás elementos en la cola de prioridad en K
        while (!pq.isEmpty() && pq.peek() < newX) {
            int y = pq.poll();
            int yFreq = map.get(y);
            map.put(y, yFreq - 1); // Actualizar frecuencia de y en el mapa
            pq.offer(y - K); // Decrementar y en K e insertarlo de nuevo en la cola de prioridad
        }

        // Actualizar frecuencia de x en el mapa
        map.put(x, 0); // Eliminar x del mapa
        map.put(newX, map.getOrDefault(newX, 0) + freq);

        pq.offer(newX); // Insertar el nuevo elemento (x+K) de nuevo en la cola de prioridad
    }

    return count; // Devolver el recuento máximo de cualquier elemento
}

public static void main(String[] args) {
    int[] A = {3, 1, 3};
    int K = 1;
    System.out.println(reduceDistinct(K, A)); // Salida: 3

    A = new int[] {1, 2, 2};
    K = 1;
    System.out.println(reduceDistinct(K, A)); // Salida: 2
}

}
“`</integer,>

Answer

davy.ai

August 6, 2023 at 12:29 pm
El problema dado se puede resolver en una complejidad de tiempo O(n log n) utilizando una cola de prioridad. Aquí están los pasos:
1. Inicializar una cola de prioridad (montículo mínimo) con todos los elementos del arreglo dado.
2. Inicializar un mapa para almacenar la frecuencia de cada elemento en la cola de prioridad.
3. Inicializar una variable “count” para almacenar el recuento máximo de cualquier elemento (inicializado en 1).
4. Ahora, para cada elemento en la cola de prioridad, hacer lo siguiente:
  a. Obtener el elemento con el valor mínimo (digamos x) de la cola de prioridad y eliminarlo.
  b. Incrementar el recuento de x en el mapa.
  c. Agregar K a x e insertarlo de nuevo en la cola de prioridad.
  d. Decrementar todos los demás elementos en la cola de prioridad en K.
  e. Si el nuevo elemento x después de la adición de K sigue siendo menor o igual al elemento mínimo en la cola de prioridad, entonces repetir los pasos a-e hasta que esta condición sea falsa.
  f. Actualizar el recuento máximo “count”.
5. Devolver el recuento máximo “count” como respuesta.
Aquí está el código en Java que implementa el algoritmo anterior:

“`java
import java.util.*;

public class ReduceArrayDistinct {
public static int reduceDistinct(int K, int[] A) {
// Inicializar cola de prioridad con todos los elementos del arreglo
PriorityQueue pq = new PriorityQueue<>();
for (int x : A) {
pq.offer(x);
}
```
    // Inicializar mapa para almacenar la frecuencia de cada elemento en la cola de prioridad
    Map<integer, integer=""> map = new HashMap<>();
    for (int x : A) {
        map.put(x, map.getOrDefault(x, 0) + 1);
    }

    int count = 1; // Recuento máximo de cualquier elemento

    // Procesar cada elemento en la cola de prioridad
    while (!pq.isEmpty()) {
        int x = pq.poll(); // Obtener el elemento mínimo de la cola de prioridad
        int freq = map.get(x);
        count = Math.max(count, freq); // Actualizar recuento máximo

        int newX = x + K; // Agregar K a x

        // Decrementar todos los demás elementos en la cola de prioridad en K
        while (!pq.isEmpty() && pq.peek() < newX) {
            int y = pq.poll();
            int yFreq = map.get(y);
            map.put(y, yFreq - 1); // Actualizar frecuencia de y en el mapa
            pq.offer(y - K); // Decrementar y en K e insertarlo de nuevo en la cola de prioridad
        }

        // Actualizar frecuencia de x en el mapa
        map.put(x, 0); // Eliminar x del mapa
        map.put(newX, map.getOrDefault(newX, 0) + freq);

        pq.offer(newX); // Insertar el nuevo elemento (x+K) de nuevo en la cola de prioridad
    }

    return count; // Devolver el recuento máximo de cualquier elemento
}

public static void main(String[] args) {
    int[] A = {3, 1, 3};
    int K = 1;
    System.out.println(reduceDistinct(K, A)); // Salida: 3

    A = new int[] {1, 2, 2};
    K = 1;
    System.out.println(reduceDistinct(K, A)); // Salida: 2
}
```
}
“`</integer,>

Comments are closed.

es.davy.ai

¿Tienes una pregunta?

Reducir la cantidad de elementos distintos en el arreglo

Answer

davy.ai