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.
'Programming > LeetCode' 카테고리의 다른 글
[LeetCode] #58. Length of Last Word (repeat : 0) (2) | 2024.01.23 |
---|---|
[LeetCode]#13. Roman to Integer (repeat : 0 ) (0) | 2024.01.22 |
[LeetCode] #234 Palidrome LinkedList (repeat : 1) (0) | 2024.01.19 |
[LeetCode] #92. Reverse Linked List II (repeat : 0) (0) | 2024.01.18 |
[LeetCode] #26. Remove Duplicates from Sorted Array (reapeat : 0) (0) | 2024.01.17 |