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; } |
Referencia:
Un algoritmo de voto mayoritario en tiempo lineal