行内に1の最大数を見つける

Question

2次元マトリックスは、1と0で埋められています。 1つの行のすべての1がすべての0の前に来ることが与えられます。私たちは1行の最大数を見つける必要があります。

私は、すべての行で最後の1のインデックスを取得するために、その行の最後のインデックスを0から始めることができるというソリューションを作成しました。 1のインデックスは+1になります。だから私たちはすべての行でこれを行うことができます。 複雑さはO（mlogn）になります。ここで、mはnoです。 nはノーです。列の もっと良い解決策がありますか？

Answer 1

O（n + m）で実行できます。

curmax = 0で開始してください。

次に、行を1つずつ処理します。その行に少なくともcurmax 1がある間、curmaxを増加させる、すなわちcurmax値が1であるかどうかをチェックする。

すべての行が処理された後、答えはcurmax-thになります。

これはO（n + m）で機能します。

O（m * logn）よりも速いでしょうか？場合によります。もしmがn /（log（n） - 1）より小さければ、実際にはO（m * log n）より長く、そうでなければより複雑である。
時間を近似すると、定数を考えることも別の問題です。ですから、1つのマグニチュードのnとmの方が速くなります。

Answer 2

あなたは最大値にのみ関心があるので、すべての行に対してスイッチの位置を見つける必要はありません。

k（0）の最初の行のスイッチ位置が見つかったら、位置k（0）から2番目の行を検索し、0の場合は2番目の行に最長のシーケンスあなたはそれが実際にどこにあるかを無視することができます。これは、最悪の場合の時間の複雑さを改善するものではありませんが、平均的なケースを改善します。

Answer 3

行をチェックして、前の行で停止した位置から次の行を開始するだけです。その値が0の場合は、次の行に進みます。最後の行まで手順を繰り返します。

Answer 4

1  bool matrix[100][200]; 
2  int max = 0, count, x; 
3  
4  for(int y=0;y<100;y++){ 
5   count = 0; 
6   x=max; // This would optimize the search times! 
7   for(;x<200;x++){ 
8    if(matrix[y][x] == 0 && count>max){ 
9    max=count; 
10   } 
11   else count++; 
12  } 
13  if(x == 199)break; // Optimization - the end reached 
14 } 
15 
16 // Now the max var contains the maximum number of 1's of a single row in all columns. 

各行を歩く代わりに、既知の位置をスキップするだけです。 この最適化は行6に実装されています。

Answer 5

O（n + m）アルゴリズムの要点はこれです。

グリッドとしてあなたのマトリックスを想像してください。

左上隅から開始します。

あなたが1の場合は、右に移動します。そうでなければ下に移動します。

最後の行を渡すまでこれを続けます。

あなたのx座標は1の最大数です。

すべて1の行がある場合は、最後の列より1つ先に移動することができます。あなたのアルゴリズムはこれに対応する必要があります。

Answer 6

上記のコードのように、最大​​数が1の行列の最初の行にない場合は、max変数を間違って更新するため、行番号5、つまりcount = 0が最初のループから抜ける必要があります。

public static int findRowWithMax1s(int arr[][],int m, int n){ 

    int x,y,count=0,max=0; 
    int row = 0; 
    for(x=0;x<m;x++) { 
     y = max; 
     for(;y<n;y++) { 
      if(arr[x][y] == 0) { 
       max = count; 
       row = x; 
       break; 
      } 
      else 
       count++; 
     } 
    } 

    return max; 
} 

Answer 7

#include <stdio.h> 
#define R 4 
#define C 4 

/* A function to find the index of first index of 1 in a boolean array arr[] */ 
int first(bool arr[], int low, int high) 
{ 
    if(high >= low) 
    { 
    // get the middle index 
    int mid = low + (high - low)/2; 

    // check if the element at middle index is first 1 
    if ((mid == 0 || arr[mid-1] == 0) && arr[mid] == 1) 
     return mid; 

    // if the element is 0, recur for right side 
    else if (arr[mid] == 0) 
     return first(arr, (mid + 1), high); 

    else // If element is not first 1, recur for left side 
     return first(arr, low, (mid -1)); 
    } 
    return -1; 
} 

// The main function that returns index of row with maximum number of 1s. 
int rowWithMax1s(bool mat[R][C]) 
{ 
    int max_row_index = 0, max = -1; // Initialize max values 

    // Traverse for each row and count number of 1s by finding the index 
    // of first 1 
    int i, index; 
    for (i = 0; i < R; i++) 
    { 
     index = first (mat[i], 0, C-1); 
     if (index != -1 && C-index > max) 
     { 
      max = C - index; 
      max_row_index = i; 
     } 
    } 

    return max_row_index; 
} 

/* Driver program to test above functions */ 
int main() 
{ 
    bool mat[R][C] = { {0, 0, 0, 1}, 
     {0, 1, 1, 1}, 
     {1, 1, 1, 1}, 
     {0, 0, 0, 0} 
    }; 

    printf("Index of row with maximum 1s is %d n", rowWithMax1s(mat)); 

    return 0; 
}