Count the Number of 1’s in
each row:
Given a boolean matrix with
every row sorted, find the row with maximum number of 1s.
package core.geeks;
import java.io.PrintStream;
public class MaxNum1SortedMatrix {
static PrintStream out = java.lang.System.out;
public static void main(String[]
args) {
int[][]
sortedMatrix = {{0,0,0,1,1,1},
{0,0,1,1,1,1},
{0,0,0,0,1,1},
{1,1,1,1,1,1},
{0,0,1,1,1,1}};
int row =
sortedMatrix.length-1;
int column
= sortedMatrix[0].length-1;
int[] resultArr
= new int[row+1];
for (int i = 0;
i <=row; i++) {
int[] temp =
sortedMatrix[i];
resultArr[i] = column - binarySerachIdx(temp)+1;
}
for (int i = 0;
i < resultArr.length; i++) {
System.out.println(resultArr[i]);
}
}
private static int binarySerachIdx(int[] temp) {
int start =
0; int mid =
temp.length/2;
while(start<mid)
{
if(temp[mid]==1
&& mid>0 && temp[mid-1]==1) {
mid = mid-1;
} else if(temp[mid]==0
&& mid<temp.length) {
start = mid;
mid = temp.length-1;
} else {
return mid;
}
}
return 0;
}
}
Output:
3
4
2
6
4
No comments:
Post a Comment