Input:

[1, 0, 1],
[0, 1, 0],
[1, 0, 1]

Output: [2, 1, 2]

For this example, n = number of rows or columns

For the given binary matrix, can I get an array of the count of 1's in each row in O(n) time complexity?

CodePudding user response：

You can use this:

int a[] = {1, 0, 1};  //You can also use double dimension array
int b[] = {0, 1, 0};  //instead of three arrays.
int c[] = {1, 0, 1};
int count[] = {0, 0, 0};
for(int i = 0; i < a.length; i  ){
    if(a[i] == 1)
        count[i]  ;
}
for(int i = 0; i < b.length; i  ){
    if(b[i] == 1)
        count[i]  ;
}
for(int i = 0; i < c.length; i  ){
    if(c[i] == 1)
    count[i]  ;
}
System.out.println("Output:");
for(int i = 0; i < count.length; i  ){
    System.out.println(count[i] "  ");
}

I prefer using double dimension array here but even this will work.

CodePudding user response：

If N is the number of rows, then there is no O(N) solution. You need to visit each cell. There are N^2 cells so the complexity is O(N^2).

If you represent the matrix using bits (0 or 1) rather than integer counts, you can do the bit counting faster than iterating the bits. However, there are still O(N^2) bits in the matrix. Even if you pack them 32 or 64 bits per word, you still have O(N^2) words to visit... so the complexity remains the same.