Categorías
Algorithms Interview

LeetCode – Elemento mayoritario II (Java)

Dada una matriz entera de tamaño n, encuentre todos los elementos que aparecen más de ⌊ n / 3 ⌋ veces. El algoritmo debe ejecutarse en tiempo lineal y en espacio O (1).

Solución Java

Este problema es similar al Elemento Mayoritario I. Tiempo = O (n) y Espacio = O (1).

public List<Integer> majorityElement(int[] nums) {
    List<Integer> result = new ArrayList<>();
 
    Integer n1 = null, n2 = null;
    int c1 = 0, c2 = 0;
 
    for (int i : nums) {
        if (n1 != null && i == n1.intValue()) {
            c1++;
        } else if (n2 != null && i == n2.intValue()) {
            c2++;
        } else if (c1 == 0) {
            c1 = 1;
            n1 = i;
        } else if (c2 == 0) {
            c2 = 1;
            n2 = i;
        } else {
            c1--;
            c2--;
        }
    }
 
    c1 = c2 = 0;
 
    for (int i : nums) {
        if (i == n1.intValue()) {
            c1++;
        } else if (i == n2.intValue()) {
            c2++;
        }
    }
 
    if (c1 > nums.length / 3)
        result.add(n1);
    if (c2 > nums.length / 3)
        result.add(n2);
 
    return result;
}
  LeetCode - Kth elemento más pequeño en una matriz ordenada (Java)

Referencia:
Un algoritmo de voto mayoritario en tiempo lineal

Por Programación.Click

Más de 20 años programando en diferentes lenguajes de programación. Apasionado del code clean y el terminar lo que se empieza. ¿Programamos de verdad?

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *