sábado, 30 de octubre de 2010

Elemento mayoritario (solución lineal para n par)

El elemento mayoritario de un vector se define como el elemento que pertenece al vector y que se repite más de n/2 veces; donde n es el numero de elementos del vector.

El problema consiste en determinar si un vector tiene o no un elemento mayoritario y si lo tuviera decir cual es.

En internet podemos encontrar soluciones de orden asintótico O(n²) y O(n log n) para este problema. Sin embargo ¿Se podrá resolver de forma más eficiente?

La solución que presentare a continuación resuelve parcialmente este problema pues solo funciona correctamente cuando el numero de elementos del vector es par. El orden asintótico de esta solución es O(2n), es decir, es de tiempo lineal.

Básicamente lo que hace este algoritmo es, en un primer recorrido, buscar un candidato que pudiera ser el elemento mayoritario. Y con un segundo recorrido determinar si ese candidato efectivamente es el elemento mayoritario. Si no lo fuera entonces el vector no tiene un elemento mayoritario.

Para buscar el candidato partimos de la condición de que el elemento mayoritario debe aparecer repetido mas de n/2 veces en el vector. Esto se traduce a que, cuando n es un numero par, al menos una vez el elemento mayoritario debe aparecer en posiciones consecutivas. Por lo tanto el candidato sera el elemento que aparezca mas veces de forma consecutiva. Esto puede lograrse en un solo recorrido del vector.

Finalmente, con un segundo recorrido se cuenta cuantas veces se repite el candidato y si es mayor a n/2 se concluye que ese es el elemento mayoritario. Si no lo fuera se puede concluir que el vector no tiene ningún elemento mayoritario.

La implementación del algoritmo en C++:

/*
Problema del elemento mayoritario (solucion lineal para n par)
Por: Alguien
Fecha: Jueves 28 de octubre del 2010
*/

#include <stdio.h>
#include <stdlib.h>

bool buscar(int *v, int n, int *may);

int main() {
 int *v, n;
 printf("n = ");
 scanf("%d", &n);
 if(n%2 != 0) {
  printf("n debe ser par.\n");
  return -1;
 }
 v = new int[n];
 for(int i=0; i<n; i++) {
  printf("v[%d] = ", i);
  scanf("%d", &v[i]);
 }
 
 int may=0;
 if(buscar(v, n, &may))
  printf("mayoritario = %d\n", may);
 else
  printf("no hay elemento mayoritario.\n");
 return 0;
}

bool buscar(int *v, int n, int *may) {
 //busqueda
 int rep=1, mrep=rep, ant=v[0];
 for(int i=1; i<n; i++) {
  if(v[i] == ant) {
   if(++rep > mrep) {
    *may = v[i];
    mrep = rep;
   }
  } else {
   ant = v[i];
   rep = 1;
  }
 }

 //Comprovacion
 rep = 0;
 for(int i=0; i<n; i++)
  if(v[i] == *may)
   rep++;
   
 //respuesta
 if(rep > n/2)
  return true;
 return false;
}

Saludos.

Actualización:

Este algoritmo falla para algunos casos. Ver otra propuesta en:

http://alguienenlafisi.blogspot.com/2010/11/elemento-mayoritario-solucion-lineal.html

No hay comentarios:

Publicar un comentario