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