Leet code Majority element
This is not a review, but an extended comment.
Theoretically you are right, a time complexity of the first approach is \$O(n)\$. However, there is also a space complexity, also \$O(n)\$, due to the Map, and the map is a very heavyweight data structure. Even though it promises a constant time access, it is only an amortized constant time, and the constant could be quite large. You must also take into account its cache unfriendlyness.
Meanwhile, both approaches are suboptimal. There is a way to solve the problem in a linear time in constant space.