Tuesday, July 16, 2019

#codingexercise
Find an element in a sorted matrix

The downward or to the right front propagation from top-left corner allows linear time search for an element in the sorted matrix.
void printSerialized(int[ ][ ] A, int rows, int cols)
{
if ( A== null || rows == 0 || cols == 0) return;

var items = new List<Pair<int,int>>();
items.Add(new Pair<int,int>(0,0));

while ( items.Count != 0 )
{

// print current min
var item = removeMinValue(items);
System.out.println(item.GetValue());

// add next candidates
var down = new Pair<int,int>(item.first+1, item.second);
var right = new Pair<int,int>(item.first,item.second+1);
if (IsValid(down) && items.Contains(down) == false)
    items.Add(down);
if (IsValid(right) && items.Contains(right) == false)
    items.Add(right);
}
System.out.println(A[r][c]);
}

No comments:

Post a Comment