3

この質問はインタビューで私に尋ねられました。線形時間と一定のメモリで最大値のすべての出現を見つけることができる場合、整数のソートされていないリストが与えられます。

当時は答えられず、中央値の中央値アルゴリズムに出くわしました。この場合、このアルゴリズムが適用可能かどうかはまだわかりません。

4

6 に答える 6

3

セットの最大値はO（n）で見つけることができます。リストに目を通し、最大値を更新するだけです。

max = int_array[0]
for i = 1 to int_array.size():
    if int_array[i] > max:
        max = int_array[i]

次のパスでは、そのようなすべての要素で目的の機能を呼び出すことができます。たとえば、彼らの位置、そして最後に彼らの数を印刷したい場合：

count = 0
for i = 0 to int_array.size():
    if int_array[i] == max:
        print "Index i"
        count += 1
print count

最初のパスでカウントをいつでも決定できます。現在の要素が最大に等しい場合は常にカウントを増やし、現在の最大値を変更するたびにカウントをリセットします（たとえば、現在の要素が現在の最大値よりも大きい場合）。同様に、最初のパスで最大値の位置を思い出すことができます。したがって、すべてを1つに統合します。

count = 1
max = int_array[0]
indexes = [0]
for i = 1 to int_array.size():
    if int_array[i] == max:
        count += 1
        indexes.insert(i)
    else if int_array[i] > max:
        count = 1
        indexes = [i]
        max = int_array[i]
print "There are " + count + " elements with maximal value of " + max
print "On positions: "
for int i = 0 to count:
    print indexes[i]
于 2012-05-14T06:26:55.607 に答える
2

最大のすべてのインスタンスの位置を記録するシングルパスソリューションは次のとおりです。

set POS //where the maxima are, initially empty
max = A[1]//first element
add 1 to POS

for i = 2 to n
  if A[i] > max
    max = A[i]
    empty POS
    add i to POS
  if A[i] == max
    add i to POS

return POS

最大のすべてのオカレンスの位置を保存する必要があるため、O(n + count(max))メモリ使用量はです。O(n)

于 2012-05-14T07:57:33.903 に答える
2

これは、最大値を見つけて、最大値が見られたすべてのリストインデックスを記録するためのワンパスソリューションです。

O(n)リストのインデックスを記録する場合は、メモリを使用します。最大値が発生する回数だけをカウントしたい場合は、リストをカウンターに置き換えれば、O(1)メモリがあります。*

numbers = [ ... list of numbers ... ]
largest_seen = - Infinity
positions_seen_at = [ empty list ]

for ( i = 0; i < len(numbers); i++ ):
    if numbers[i] > largest_seen:
        largest_seen = numbers[i]
        positions_seen_at = [ empty list ]

    if numbers[i] == largest_seen:
        positions_seen_at.append(i)

*「合理的な」サイズの入力を想定しています。入力リストのサイズが非常に大きい場合は、カウンターを保持するために任意の長さの整数が必要になる場合があります。それはO(log n)記憶になります。

于 2012-05-14T08:18:11.213 に答える
1

最大値は中央値よりはるかに簡単です

Pythonでは、数字のリストがLの場合、これと同じくらい簡単です。

L.count(max(L))

L.countはO（n）
ですmax（L）もO（n）です

この単純なソリューションは、各要素を2回調べますが、アルゴリズムは全体としてO（n）のままです。

于 2012-05-14T06:58:41.483 に答える
1

このような詳細な回答をありがとうございました。少し考えた後、ソートされていないリストの1回のパスで最大アイテムと最大アイテムのすべてのオカレンスを提供するソリューションがあると思います。ああ！私は数日前にそれを思い付くことができたかもしれません:)しかし決して遅くなるよりはましです...

これが私が書いたJavaコードスニペットです：

public int getNumberOfOccurrencesOfMax(List<Integer> inputList){ 

if(this.inputList.size() == 0) 
     return 0;
Integer max = Integer.MIN_VALUE, max_occurances = 0;

for(int i=0; i < inputList.size(); i++){
        if(max < this.inputList.get(i)){
            max = this.inputList.get(i);
            max_occurances = 1;
        }
        else if(max > this.inputList.get(i)){
            max_occurances = (max_occurances > 0) ? max_occurances : 1; 
        }
        else{
            max_occurances += 1;
        }
    }
return max_occurances;
} // END_OF_METHOD

（1,1,2,2,3,4,4,5,5,5）のサンプルリストを使用してコードを試しました。

私の実装に対する改善を提案してください。

一番、

于 2012-05-15T01:40:34.867 に答える
0

これもうまくいくと思います：

O（n）アルゴリズム

i = 0
highestStart = 0
size = array.size
for i < size -1 
     if array[i] > array[i+1]
          x = array[i]
          delete array[i] //remove higher value
          array[array.size] = x  // push higher value to the end
          highestStart = i
      else if array[i] < array[i+1]
          highestStart = i+1
     end if
  end if
  i = i+1
end for
return subarray[highestStart, array.size -1]

1*,5*,4 ,7 ,9 ,4 ,9   :0,1
1 ,5*,4*,7 ,9 ,4 ,9   :1,2
1 ,4 ,7*,9*,4 ,9 ,5   :2,3
1 ,4 ,7 ,9*,4*,9 ,5   :3,4
1 ,4 ,7 ,4 ,9*,5*,9   :4,5
1 ,4 ,7 ,4 ,5 ,9*,9*  :5,6
于 2012-05-14T06:53:01.163 に答える