✍️

【C言語】Leet Code Probrems「169. Majority Element」解答例

2023/01/09に公開約1,000字

はじめに
本記事ではLeetCodeの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.

https://leetcode.com/problems/majority-element/

解答例
※Listの数が多いテストケースの演算に時間がかかってしまうロジックのため、「Time Limit Exceeded」で提出できてない不完全なコードになります。

int majorityElement(int* nums, int numsSize){

    int count=0;
    int max=0;
    int ans=0;

    if(numsSize==1){
        return nums[0];
    }

    for(int i=0;i<numsSize;i++){
        for(int j=0;j<numsSize;j++){
            if(nums[i]==nums[j]){
                count++;
            }
        }
        if(count>max){
            max=count;
            ans=nums[i];
        }
        count=0;
    }
    return ans;
}

方針
①配列の数値の数を全てカウントする
②カウントして現在の最大値より大きければ更新する

結果
リストの数が少ないテストケースでは期待結果を出すことができたが、多い場合、演算に時間がかかりNGとなってしまった。
原因は2重ループで演算量が多いことだと思われる。

感想
他のユーザーの解答例を見るとfor文一つで演算しているケースが多かった。
LeetCodeのEasyの問題を数題解いてみて、1~2h程度で回答を出せるようになっているが、
効率的な計算を考えずに冗長な演算をしているので、演算量を減らせるか考えていく

Discussion

ログインするとコメントできます