[LeetCode] 169. Majority Element

Problem

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Example 1:

Input: nums = [3,2,3]
Output: 3

Example 2:

Input: nums = [2,2,1,1,1,2,2]
Output: 2

Constraints:

• n == nums.length
• 1 <= n <= 5 * 10^4
• -10^9 <= nums[i] <= 10^9

Follow-up: Could you solve the problem in linear time and in O(1) space?

Solution

Logic

1. 배열을 오름차순으로 정렬시킨다.

2. 배열의 중앙에 위치한 요소를 반환한다.

   Code

   class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }
   }
   

   Time Complexity

   • 배열의 길이를 n이라 가정할 떄, 코드의 수행 시간을 좌우하는 것은 배열을 정렬하는 메서드의 계산 횟수이다. 해당 메서드가 O(nlogn)의 시간 복잡도를 가지므로 본 솔루션은 O(nlogn)의 시간 복잡도를 가진다.