最大発生数が1の行を見つけよう

Question

インタビューでこの質問に出会った。 1と0を含むnxn行列があります。あなたは最も効率的な方法で1の最大数を含む行を見つける必要があります。私はそれがn^2で行うことができることを知っていますが、これには最適なソリューションがありますか？

Answer 1

最適解はO（n^2）です。行列にゼロのみが含まれているとします。あなたはこれを確かめるためにすべてのセルを調べなければなりません。これはO（n^2）です。

アルゴリズムを最適化すると、1だけしか含まれていない行が見つかった場合（最適でなければならない）、行内に非常に多くの零点があると見なして、遠いこれは場合によっては大幅なスピードアップをもたらす可能性がありますが、一般的なケースではまだO（n^2）になります。

Answer 2

最適化として、列を解析してから1行あたり最大1を計算します。 n/2ステップ後に、適切でない行を排除し始めます。 (The rows with MAX number of 1s - rowSum(number of ones in that row) > (the number of columns unchecked) - 複雑度O(n^2)

Answer 3

最悪の場合の複雑さは、とにかくO（n ）になります。

しかし、定数と一般的な複雑さを減らすことができます。

＃(x < n)行数を計算します。

残りのn-x行については、停止すると、その行からbextの回答を見つけることができなくなります。

ここでポイントはxの最適値を得ることです。

PS：類似しています - あなたが3回しか選べないという条件で、100人の中から最高の人を選んでください。

Answer 4

JavaScriptで最も効率的な実装です。

上記の回答と同様です。 N 1で行をヒットした場合は短絡し、現在の行が1より大きい可能性がない場合は外部（行）ループを継続します。

しかし、この回答は、関係する条件付きロジックを効率的に使用（読み込み：配置）することも示しています。最悪の場合は、したがって、問題はそれを見つけることに減らし、あなたがそれらをすべて確認する必要があり、マトリックス全体に一つだけ1があるということですので、

// return the smallest row index 0 - (N-1) containing the greatest number of 1's 
function MaxRow(M, N) { 
// initialize max to 0 if you want to return null for an all zero matrix 
// initialize max to -1 if you want to return 0 (row 0) for an all zero matrix 
var max = 0; 
var result = null; 
var row1s; 
rowLoop: 
for(var row = 0; row < N; row++) { 
    row1s = 0; 
    for(var col = 0; col < N; col++) { 
     if((N - col) + row1s < max) { // row's current potential 1's 
      continue rowLoop; // next row 
     } 
     row1s += M[row * N + col]; // + 0 or + 1 
    } 
    if(row1s > max) { // new max 
     max = row1s; // save new max value 
     if(max == N) { // largest possible 
      return row; 
     } 
     result = row; 
    } 
} 
return result; 
}