[LeetCode] #169. Majority Element (repeat : 0 )

Description

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

Solution  

Arrays.sort(nums);
int result = nums[nums.length/2];
return result;

 

Approach

In the description , It says 'The majority element is the element that appears more than n/2 times'

It means the majority element appears more than half number of array'length. 

For example, when it is [1,2,3,3,5], n is 5 so the majority element should appear more than L5/2 = 2.

Another example, When it is  [2,2,1,1,1,2,2] , n is 7 , so the majority element should appear more then L7/2 = 3. 

 

In this algorithm,  This is the setted condition so I dont have to consider other cases except 'the majority element appears half num of the array's length'

Since the majority element appears more than half, majority element will be always in the middle

So I sorted the array in the non-decreasing order, and then returned the index nums.length/2.

 

Complexity

In terms of time complexity it is O(n log n) . because It checks only half of the array.

In terms of space complexity, it is O(1) since it uses only constant number of variable.