LeetCode – Elemento mayoritario (Java)

Dada una matriz de tamaño n, encuentre el elemento mayoritario. El elemento mayoritario es el elemento que aparece más de ⌊ n / 2 ⌋ veces. (suponga que la matriz no está vacía y que el elemento mayoritario siempre existe en la matriz).

Solución 1 de Java: clasificación

Suponiendo que exista la mayoría y dado que la mayoría siempre ocupa más de la mitad del espacio, se garantiza que el elemento intermedio será la mayoría. La matriz de clasificación toma O (nlog (n)). Entonces, la complejidad temporal de esta solución es nlog (n).

public int majorityElement(int[] num) {
	if (num.length == 1) {
		return num[0];
	}
 
	Arrays.sort(num);
	return num[num.length / 2];
}

Solución Java 2 – Algoritmo de voto mayoritario

Este problema se puede resolver en el tiempo de O (n) con una complejidad espacial constante. La idea básica es que el elemento mayoritario puede negar la cuenta de todos los demás elementos.

public int majorityElement(int[] nums) {
    int result = 0, count = 0;
 
    for(int i = 0; i<nums.length; i++ ) {
        if(count == 0){
            result = nums[ i ];
            count = 1;
        }else if(result == nums[i]){
           count++;
        }else{
           count--;
        }
    }
 
    return result;
}

Referencia:
Un algoritmo de voto mayoritario en tiempo lineal