행의 최대 수를 찾습니다.

Question

2 차원 행렬은 1과 0으로 채워집니다. 모든 1이 연속적으로 모든 0보다 먼저옵니다. 우리는 연속으로 최대 1의 숫자를 찾아야합니다.

나는 따라서의 시작 우리가 영하기 전에 해당 행의 마지막 1의 마지막 인덱스를 얻기 위해 모든 행에 이진 검색을 적용 할 수있는 솔루션을 만들었습니다 없음. 1의 인덱스가 +1됩니다. 그래서 우리는 모든 행에서 이것을 할 수 있습니다. 그래서 복잡성은 O (mlogn)가 될 것입니다. 여기서 m은 no입니다. n 개의 행이 있습니다. 열의 더 좋은 해결책이있을 수 있습니까?

Answer 1

O (n + m)에서 수행 할 수 있습니다.

시작 하나이어서 0

처리 한 행과 동일한 curmax. 그 행에 적어도 curmax 값이있는 동안, 즉 curmax 값이 1인지를 확인하면서 curmax를 증가 시키십시오.

모든 행을 처리 한 후 답이 curmax-th가됩니다.

O (n + m)에서 작동합니다.

O (m * logn)보다 빠릅니까? 그것은 달려있다. 만약 m이 n/(log (n) - 1)보다 작 으면, 실제로는 O (m * log n)보다 길고 그렇지 않으면 더 복잡합니다.
시간을 근사 할 때 상수를 고려하는 것이 다른 문제입니다. 따라서 n과 m의 크기가 더 빠를 것입니다. 다른 경우에는 하나만 선택해야합니다. 둘 다 시도하고 더 잘 선택하십시오.

Answer 2

최대 값에만 관심이 있으므로 모든 행에 대해 스위치의 위치를 ​​찾을 필요는 없습니다.

첫 번째 행의 스위치 위치가 발견 된 후 k (0)에서 두 번째 행을 검색하고, 0이면 두 번째 행에 가장 긴 시퀀스가 ​​포함되지 않으므로 실제로 어디에 있는지 무시할 수 있습니다. 이것은 최악의 경우의 시간 복잡도를 향상시키지 않지만 평균의 경우를 향상시킵니다.

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의 행이있는 경우 마지막 열을지나 한 행 이동할 수 있습니다. 귀하의 알고리즘은이를 충족시켜야합니다.

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; 
}