http://www.geeksforgeeks.org/majority-element/

여기 가보시면 O(n)만에 MN을 구하는 알고리즘이 설명되어있긴 합니다...증명까진 못하겠네욬ㅋㅋ

d&c로 하면 시간복잡도가 O(n logn)이 나오는데, 이것보다 더 짧은 방법을 찾으시는건가요?

기본적으로 어떤 수 x 가 MN 이면 주어진 숫자들을 두 개씩 짝을 만들면 비둘기집의 원리에 따라 MN 인 녀석은 MN 인 녀석끼리 짝이 지어지거나 혼자남거나 둘 중 하나의 경우 밖에 없고 대우명제를 증명해서 O( N ) 알고리즘을 증명하면 될 것 같아요

잘 이해가 안되서 질문드립니다. 분할 정복으로 정렬을 수행하면 MN이 구해지는거 아닌가요?

그 외의 다른 방법을 찾으시는건가요?