【LeetCode】Majority Element解題レポート

Majority Element
[LeetCode]
https://leetcode.com/problems/majority-element/
Total Accepted: 110538 Total Submissions: 268289 Difficulty: Easy
Question
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.
Ways
第一のアイデアは、HashMapを使います.うん.前にもやったことがありますが、考えてみれば間違っていて、効率が悪いに違いありません.
そしてあまり良い方法も思いつかなかった.しかし、政府はいくつかの考えを与えました.
時間の複雑さ:O(n 2)—蛮力法:各要素が衆数であるかどうかを順次チェックする
時間複雑度:O(n)、空間複雑度:O(n)-ハッシュ・テーブル:各要素の出現回数のハッシュ・テーブルを維持し、出現回数が最も多い要素を見つけます.
時間の複雑さ:O(n log n)—ソート:ソート後に連続的に繰り返される回数が最も多い要素を見つけます.
平均時間複雑度:O(n)、最悪複雑度:無限大-ランダムアルゴリズム:ランダムに1つの要素を選択して衆数であるかどうかを計算する.そうでなければ、見つけるまで前の手順を繰り返します.衆数が選ばれる確率は1/2であるため、所望の試行回数<2
時間複雑度:O(n log n)−分治法:配列を2半に分解し,前半の衆数Aと後半の衆数Bを探し出す.全体の衆数はAかBかである.A==Bであれば,自然とグローバル衆数である.そうでなければ、AとBはいずれも候補数であり、せいぜいこの2つの要素の出現回数を調べるだけでよい.時間複雑度、T(n)=T(n/2)+2 n=O(nlog n)である.
時間複雑度:O(n)-Moore投票アルゴリズム:現在の候補衆数と初期0のカウンタを維持します.配列を巡るとき、現在の要素xを見てみましょう.
カウンタが0である場合、我々は候補衆数をxにし、カウンタを1にする.カウンタが0でない場合、我々はxと現在の候補衆数がカウンタ+1または-1に等しいかどうかによって、現在の候補衆数が求められる衆数である.時間複雑度=O(n).時間複雑度:O(n)−ビット操作法:全n個数のi番目のビットの1の個数を計算するたびに32回の反復が必要である.衆数が必ず存在するため、1の個数0の個数または逆(ただし決して同じではない)である.衆数のi位はカウントの多い数字に違いない.
この投票方法はとても面白いです.多数派の問題だ.
この考え方はこうです.
viの場合、cが未知の状態である場合、c=v[i]、t=1、iがインクリメントされる.c=v[i],++tの場合、iがインクリメントされる.もしc!=v[i],–t,t=0の場合,cを未知の状態にしてiをインクリメントする.すべての投票処理が完了した後、cが未知の状態であれば、いかなる候補の得票数が半分を超えていないことを示し、そうでなければ配列vを再遍歴し、候補cの実際の得票総数を統計し、cの得票数が確かに半分を超えていれば、cは最終結果である.
例えばデータ[1,2,1,1,3,1,4,4]について

i       1   2   3   4   5   6   7   8
v[i]    1   2   1   1   3   1   4   4
c       1   ?   1   1   1   1   1   ?
t       1   0   1   2   1   2   1   0

プログラム実行の最終結果,cは未知の状態にあり,投票配列vに対して候補者の得票数の過半数が存在しないことを示す.
v[1…9]={1,2,1,1,3,1,4,4,1}の場合,cの最後の状態が1である場合,配列vを再遍歴し,候補1の得票数が確実に過半数であるかどうかを調べ,統計結果1は5回出現し,9/2より大きいため,候補1の得票数は過半数である.
タイトルにはデータが半分以上存在することが保証されているからです.だからエンディングのcの要素はきっと不確定な状態ではなく、直接戻ればいいのです.
マイコード:

public class Solution {
    public int majorityElement(int[] nums) {
        int candidate=nums[0];
        int count=0;
        for(int i=0;i<nums.length;i++){
            if(count==0){
                candidate=nums[i];
                count++;
                continue;
            }
            if(candidate==nums[i]){
                count++;
            }else{
                count--;
                if(count==0){
                    candidate=-1;
                }
            }
        }
        return candidate;

    }
}

AC:3ms
参考文献:多数派問題
Date
2016/5/1 0:00:49