ソートされた配列のモードを見つけるにはどうすればいいですか？

Question

配列のモードを見つける関数を書く必要があります。私はアルゴリズムを思いつくのがうまくいかず、誰かがこれをやる方法を知っていることを期待しています。

私は配列のサイズと各要素の値を知っています。配列は最小から最大までソートされています。

アレイは

モード= FINDMODE（arrayPointer、sizePointer）のようなモード関数に渡されることになります。

UPDATE：

が、私はこの

int findMode(int *arrPTR, const int *sizePTR) 
{ 
    int most_found_element = arrPTR[0]; 
    int most_found_element_count = 0; 
    int current_element = arrPTR[0]; 
    int current_element_count = 0; 
    int count; 
    for (count = 0; count < *sizePTR; count++) 
    { 
     if(count == arrPTR[count]) 
      current_element_count++; 
     else if(current_element_count > most_found_element) 
     { 
      most_found_element = current_element; 
      most_found_element_count = current_element_count; 
     } 
     current_element = count; 
     current_element_count=1; 
    } 

    return most_found_element; 
} 

を試してみたのコメントを読んだ後、私はまだ誰も私を整理することができた場合にかかわらず、このアルゴリズムを把握する問題を抱えています。 私はベクトルを使ったことがないので、他の例を本当に理解していません。

Answer 1

set most_found_element to the first element in the array 
set most_found_element_count to zero 
set current_element to the first element of the array 
set current_element_count to zero 
for each element e in the array 
    if e is the same as the current_element 
     increase current_element_count by one 
    else 
     if current_element_count is greater than most_found_element_count 
      set most_found_element to the current_element 
      set most_found_element_count to current_element_count 
     set current_element to e 
     set current_element_count to one 
if current_element_count is greater than most_found_element_count 
    set most_found_element to the current_element 
    set most_found_element_count to current_element_count 
print most_found_element and most_found_element_count 

私は名前がそれを説明するだろうと思ったが、ここで行く：

When we start, no element has been found the most times 
    so the "high-score" count is zero. 
Also, the "current" value is the first, but we haven't looked at it yet 
    so we've seen it zero times so far 
Then we go through each element one by one 
    if it's the same as "current" value, 
    then add this to the number of times we've seen the current value. 
    if we've reached the next value, we've counted all of the "current" value. 
    if there was more of the current value than the "high-score" 
     then the "high-score" is now the current value 
    and since we reached a new value 
     the new current value is the value we just reached 
Now that we've seen all of the elements, we have to check the last one 
    if there was more of the current value than the "high-score" 
    then the "high-score" is now the current value 
Now the "high-score" holds the one that was in the array the most times! 

も注意してください。私のオリジナルのアルゴリズム/コードはバグがありました、私たちは持っていますループが終了した後、 "最後のもの"を見つけることはないので、 "現在"の余分なチェックをします。

Answer 2

ほとんどすべてがあります。

アレイがソートされていることを利用できます。

だけ配列は両方現在等しい連続番号を追跡すること、そしてあなたがその時点まで発見したに等しい連続した番号の最大数（及びその番号を生成）を通過します。最終的には、最大の等しい連続番号とそれを生成する番号が表示されます。それがモードになります。

注：ないはrelated question例one based in the histogram approachを参照、配列をソートする必要がない溶液について。

Answer 3

ヒント：

Q：どのようにしてモードを定義していますか？

A：配列内で最大の数です。

Q：順序付き配列の数値をどのように数えますか？

A：配列を繰り返し、次の項目が前の項目と等しい場合は、その値のカウントをインクリメントします。

Q：前の値のカウントが現在の値のカウントよりも小さい場合、前の値はモード？

A：いいえ

Answer 4

入力配列がソートされている場合、ここでは他の解答で説明したのと同じアプローチですが、別の方法で実装する方が理解しやすくなります。

1. 入力配列にループを実行します。
2. グローバルモード値とモードカウントを保持します。
3. 等しい要素が見つかるまで、スライドウィンドウを実行します。
4. ローカル・エレメント・カウントがグローバル・モード・カウントより大きい場合、グローバル・モードとモード・カウントを更新します。ここで

作業とC++でコードをテストしています。

int mode(vector<int> a, int N) 
{ 
    int mode = a[0]; 
    int mode_count = 1; 
    int i = 0; 
    while (i < N - 1) { 
     int cur = a[i]; 
     int cur_count = 1; 
     while (a[i] == a[i + 1]) { 
      i++; 
      cur_count++; 
     } 
     if (cur_count > mode_count) { 
      mode_count = cur_count; 
      mode = a[i]; 
     } 
     i++; 
    } 
    return mode; 
}