25번 주석에서 명시하신 동일한 카드가 몇개 있는지 탐색하는 부분은 선형탐색과 같습니다.
일반적인 경우에서 작성하신 알고리즘은 말씀하신대로 O(MlogN) 으로 작동하지만,

(1)

500000
10 10 10 ... 10
1
10

과 같은 경우 O(MN) # , 몰론 이 경우 O(M) = O(1)과 같으므로 O(N)이지만
문제에서 M은 서로 다른 정수라고 제시하지 않았으므로 

(2)

500000
10 10 10 ... 10
500000
10 10 10 ... 10

과 같은 경우도 생각할 수 있을거라고 생각합니다.
정리하자면 일반적인 경우에는 O(MlogN)이지만, 특수한 경우에는 O(MN)(O(N²))으로 
계산될 수 있다고 생각합니다.

쓰면서도 (2)와 같은 추론은 문제를 너무 억지로 해석했다고 생각하지만,
정리하면서 추론한바와 같이 O(MN)으로 계산될 수 있을 것 같긴 합니다.

그리고 글로 제시하신 딕셔너리의 경우에
M개의 정수 각각을 키값으로 하는 딕셔너리(ValueDict)를 만들고 
N개의 카드를 순서대로 읽으며, ValueDict[card[i]] += 1 과 같은 식으로 카운팅한다면
계수정렬(Counting Sort)과 같은 방식으로 출력을 포함하여 O(N+M)의 시간에 풀이할 수 있을 것 같습니다.

제 답변이 도움이 되었으면 좋겠습니다.
좋은 하루되세요!