Así, por ejemplo, la respuesta para la matriz:

1, 11, 3, 95, 23, 8, 1

sería 1, ya que todos los demás elementos solo ocurren una vez, mientras que 1 ocurre dos veces.

Muchas de las preguntas similares a esta pregunta que he visto en stackoverflow piden encontrar la mayoría absoluta (la respuesta ocurre al menos n / 2 en una matriz de longitud n), o responda la pregunta utilizando una tabla de clasificación o hash. Lo primero no es lo que pregunto, y lo segundo es demasiado lento (O (n log n) para clasificar) o usa demasiada memoria (O (n) para una tabla hash).

¿Existe tal algoritmo? Si no, ¿hay alguna prueba que demuestre por qué es imposible? Incluir una fuente sería bueno.