Majority Element[Array,Hash Table,Divide and Conquer,Sorting,Counting]

https://leetcode.com/problems/majority-element/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

 

Constraints:

• n == nums.length
• 1 <= n <= 5 * 104
• -109 <= nums[i] <= 109

 

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

 

Divide and Conquer연습을 하자.

거업나리 복잡한 개념이지만, 피할 수가 없는 영역이다 ㅠ

 

1. Python

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        def help_func(arr,left,right) -> int :
            if left==right:
                return arr[right]
            
            mid = (left+right) // 2
            left_major = help_func(arr,left,mid)
            right_major = help_func(arr,mid+1,right)
            if left_major == right_major:
                return right_major
            
            left_count = sum(1 for i in range(left,right+1) if arr[i]==left_major)
            right_count = sum(1 for i in range(left,right+1) if arr[i]==right_major)

            return left_major if left_count > right_count else right_major
        return help_func(nums,0,len(nums)-1)

 

그냥 hash table 쓰면 편하고 빠를 거 같은데,

어거지로 Divide and conquer을 쓰는 중이다.

그리고 count 하는 게 좀 신기하다. for문 안에 if문을 저렇게 마음대로 써도 되는지 싶다 ㅋㅋ;

 

--> 참고로 이 놈을 빨리 계산하는 알고리즘도 있다.

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        count = 0
        candidate = None

        for num in nums:
            if count == 0:
                candidate = num
            count += (1 if num == candidate else -1)

        return candidate

 

 

2. C++

class Solution {
public:
    int cnt(vector<int>& arr,int target,int left,int right){
        int ans = 0;
        for(int i=left;i<=right;i++){
            if(arr[i]==target) ans++;
        }
        return ans;
    }
    int help_f(vector<int>& arr,int left,int right){
        if(left==right){
            return arr[left];
        }
        int mid = (left+right)/2;
        int left_m = help_f(arr,left,mid);
        int right_m = help_f(arr,mid+1,right);
        
        if(left_m == right_m) return left_m;

        int left_cnt = cnt(arr,left_m,left,right);
        int right_cnt = cnt(arr,right_m,left,right);

        return left_cnt > right_cnt ? left_m : right_m;
    }

    int majorityElement(vector<int>& nums) {
        return help_f(nums,0,nums.size()-1);
    }
};

 

3. C

 

C랑 C++은 Counting 하는 함수도 일일히 만들어 줘야 한다. 어렵진 않지만...

int cnt(int *arr, int target, int l, int r){
    int ans=0;
    for(int i=l;i<=r;i++){
        if(arr[i]==target) ans++;
    }
    return ans;
}

int help_f(int* arr,int left,int right){
    if(left==right) return arr[left];
    
    int mid = (left+right)/2;
    int left_m = help_f(arr,left,mid);
    int right_m = help_f(arr,mid+1,right);

    if(left_m == right_m) return right_m;

    int left_c = cnt(arr,left_m,left,right);
    int right_c = cnt(arr,right_m,left,right);

    return left_c > right_c ? left_m : right_m;
}

int majorityElement(int* nums, int numsSize) {
    return help_f(nums,0,numsSize-1);
}