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