[LeetCode][169][Majority Element]

タイトルリンク:https://leetcode.com/problems/majority-element/
タイトルの説明:
Given an array of size n, find the majority element. The majority element is the element that appears more than  ⌊ n/2 ⌋  times.
You may assume that the array is non-empty and the majority element always exist in the array.
これはよくある問題です.データのセットの多くの要素(つまり、出現回数の半分以上)を見つけることです.
大学の時に先生がこの問題を話したことがあるので、ずっと印象があったので、直接考えました.
この数は出現回数が半分より大きいので,この配列の数をペアにして,異なる相殺を行い,最後に残ったのはそのmajority elementに違いない.
ここでvalueで現在比較に使用されている値を保存し、カウンタcountは比較の結果を保存します.
1.次の比較の前に、countを判断し、count==0の場合、比較する値をvalueに与え、同時にcountに1を加える.
2.count!=0、比較を行い、同じcountが1を減らさなければ、同じcountに1を加える.
3.最後のvalue値を返す
コードは次のとおりです.

int majorityElement(int num[], int n) {
    int count = 0;
    int value;
    
    for(int i = 0; i < n; i++){
        if(count == 0){
            value = num[i];
            count++;
        }else{
            if(value == num[i]){
                count++;
            }else{
                count--;
            }
        }
    }
    return value;
}

難しいのはインターネットで別のアルゴリズムを見つけて、とても良いと思って、以下のようにします:(http://blog.163.com/xie_wenbin613/blog/static/175489095201242625851399/)
分析:
1つの数字が配列に現れる回数が配列の長さの半分を超える場合、この配列を並べ替え、配列の中間位置にある数が出現回数の半分を超える数です.配列並べ替えの時間的複雑度はO(nlog(n))であるが,この問題に対しては,時間的複雑度O(n)内で求めることができるより良いアルゴリズムがある.高速ソートアルゴリズムを書いたことがありますが、Partition()メソッドは最も重要なメソッドで、indexの位置の数がソート済みであることを保証するindexを返し、indexの左側の数はindexの数よりも小さく、indexの右側の数はindexの数よりも大きいです.では、本題はこのような考え方で解くことができます.
Partition()でindexを返し、index=midの場合、配列の中位数が見つかったことを示します.indexmidの場合、中位数は[start,index-1]の間にあることを示します.最後にindex=midサイクル終了を求めることを知っています.
求めたindexに基づいて、配列を1回遍歴し、indexが指す数に等しいtime++が現れるたびに、最後にtimeが配列長の半分より大きいか否かを判断し、大きい場合はindexが指す数が求めた数であることを示し、そうでない場合は、1つの数が配列長の半分を超える回数が存在しないことを示す.