Random commentary about Machine Learning, BigData, Spark, Deep Learning, C++, STL, Boost, Perl, Python, Algorithms, Problem Solving and Web Search
Given a boolean 2D array, where each row is sorted. Find the row with the maximum number of 1s. Supposing row are sorted by ascending value.0000111000000100111110000111000011100000010001111A brute force algorithm, which scans all rows/cols counting the numbers of 1s, has n^2 complexitymax_rowmax_ones = 0for (r=0 ; r max_ones max_ones = count max_row = rreturn max_row Complexity can be reduced inverting the scan order with the following algorithm:for (c=0 ; c<N; c++) for (r=0 ; r<N; r++) if matrix[r][c] == 1 return rFabiofabioang@gmail.com
A better solution:public class SortedMatrix { static int findMaxRowWithOne(int[][] m) { int max_row = 0; int r = 0; int c = m[0].length-1; while ( (r < m.length) && (c >=0) ) { if (m[r][c]==1) { --c; max_row = r; } else { ++r; } } return max_row; } public static void main(String[] args) { int[][] m = { { 0, 0, 1, 1 }, { 0, 0, 0, 1 }, { 0, 1, 1, 1 }, { 0, 0, 1, 1 }, }; System.out.println(findMaxRowWithOne(m)); }}Fabiofabioang@gmail.com
Given a boolean 2D array, where each row is sorted. Find the row with the maximum number of 1s.
ReplyDeleteSupposing row are sorted by ascending value.
0000111
0000001
0011111
0000111
0000111
0000001
0001111
A brute force algorithm, which scans all rows/cols counting the numbers of 1s, has n^2 complexity
max_row
max_ones = 0
for (r=0 ; r max_ones
max_ones = count
max_row = r
return max_row
Complexity can be reduced inverting the scan order with the following algorithm:
for (c=0 ; c<N; c++)
for (r=0 ; r<N; r++)
if matrix[r][c] == 1
return r
Fabio
fabioang@gmail.com
A better solution:
ReplyDeletepublic class SortedMatrix {
static int findMaxRowWithOne(int[][] m) {
int max_row = 0;
int r = 0;
int c = m[0].length-1;
while ( (r < m.length) && (c >=0) ) {
if (m[r][c]==1) {
--c;
max_row = r;
} else {
++r;
}
}
return max_row;
}
public static void main(String[] args) {
int[][] m = { { 0, 0, 1, 1 },
{ 0, 0, 0, 1 },
{ 0, 1, 1, 1 },
{ 0, 0, 1, 1 }, };
System.out.println(findMaxRowWithOne(m));
}
}
Fabio
fabioang@gmail.com