3

行列の問題に遭遇しましたが、最適な解決策を見つけようとしていました。問題文は質問のトピックそのものです。さらに下を参照

Example
Input matrix

  0 1 1 1
  0 0 1 1
  1 1 1 1  // this row has maximum 1s
  0 0 0 0

Output: 2

私の解決策:行がソートされているので、各行で最初に 1 が出現するバイナリ検索を実行すると、1 のカウントは になりますtotal number of columns minus index of 1st 1。

これは で実行O(m*logn)できますが、線形時間で実行できるかどうかのロジックを知りたいと思っていました。

ありがとうございました！

4

2 に答える 2

8

右上からカーソルを開始します。各行で、行の最後の 1 に到達するまで左に進みます。次に降ります。ステップダウンしてカーソルが 0 を指している場合は、もう一度ステップダウンします。右に行くことはありません。一番左に 1 がある行を探しているので、右を見る必要はありません。実行時間は O(n+m) です。これは、すべての行を通過し、m 回ステップ ダウンし、残りの最大ステップ数が合計で n ステップになるためです。マトリックスがリストのリストであると仮定した疑似コードを次に示します。

bestrow = 0
leftmost = matrix.width

for i = matrix.height to 0:
    row = matrix[i]
    while row[leftmost - 1] == 1:
        leftmost--
        bestrow = i

return bestrow

コードを文字通りに変換すると、すべてが 0 のマトリックスで問題が発生するか、一部の行がすべて 1 である場合に問題が発生する可能性があります。これらの処理は非常に簡単で、疑似コードのポイントは一般的なアルゴリズムを伝えることです。

于 2013-07-26T05:28:31.340 に答える
0

この問題の解決策は、各行の要素数と列数によって異なります。ここにアプローチがあります。

ステップ 1: true が得られるまで、各列のすべての要素に対して単純なバイナリ && 操作を実行します。これは、少なくとも 1 つの要素を持つ列が見つかったことを意味します。これには最大 n ステップかかります。n は列の数です。

ステップ 2: 次に、その列で上から下に 1 つを検索して、最大数の 1 の行を取得します。これには最大 m ステップかかります。ここで、m は行数です。したがって、全体として O(m+n) ステップかかります。

また、同じプロパティを持つ複数の行を見つけるのにも役立ちます

于 2013-07-26T05:52:31.220 に答える