Problem
Given a matrix in which each row and each column is sorted, write a method to find an element in it.
Solution
#include <iostream>
#include <time.h>
using namespace std;
int** create_matrix(int row, int col)
{
int **m = new int* [row];
for(int i = 0; i < row; i++){
m[i] = new int[col];
}
return m;
}
void delete_matrix(int** m, int row)
{
for(int i = 0; i < row; i ++){
delete[] m[i];
}
delete []m;
}
void print_matrix(int** m, int row, int col)
{
for(int i = 0; i < row; i ++){
for(int j = 0; j < col; j++){
cout << m[i][j] << " ";
}
cout << endl;
}
}
void initial_matrix(int **m, int row, int col)
{
for(int i = 0; i < row; i++){
for(int j = 0; j < col; j ++){
m[i][j] = rand() % 100;
}
}
}
void row_bubble_sort(int **m, int row, int col)
{
for(int i = 0; i < row; i ++){
for(int j = 0; j < col - 2; j ++){
bool exchange = false;
for(int k = 0; k < col -1 - j; k ++){
if(m[i][k] > m[i][k + 1]){
int t = m[i][k];
m[i][k] = m[i][k + 1];
m[i][k + 1] = t;
exchange = true;
}
}
if(!exchange){
break;
}
}
}
}
void col_bubble_sort(int **m, int row, int col)
{
for(int i = 0; i < col; i ++){
for(int j = 0; j < row - 2; j ++){
bool exchange = false;
for(int k = 0; k < row -1 - j; k ++){
if(m[k][i] > m[k + 1][i]){
int t = m[k][i];
m[k][i] = m[k+1][i];
m[k + 1][i] = t;
exchange = true;
}
}
if(!exchange){
break;
}
}
}
}
void sort_matrix(int **m, int row, int col)
{
row_bubble_sort(m, row, col);
col_bubble_sort(m, row, col);
}
bool find(int **m, int row, int col, int x)
{
if(x < m[0][0] || x > m[row - 1][col -1]){
return false;
}
int i = 0;
int j = col - 1 ;
while (i < row && j >= 0) {
if (m[i][j] == x) {
return true;
} else if (m[i][j] > x) {
j--;
} else {
i++;
}
}
return false;
}
int main(int argc, char* argv[])
{
srand((unsigned)time(NULL));
int **matrix;
int row = 7;
int col = 5;
matrix = create_matrix(row, col);
initial_matrix(matrix, row, col);
sort_matrix(matrix, row, col);
print_matrix(matrix, row, col);
for(int i = 0; i < 10; i++){
int n = rand() % 100;
cout << n << " is found? " << find(matrix, row, col, n) << endl;
}
delete_matrix(matrix, row);
return 0;
}
Output
0 0 28 44 77
4 10 32 37 78
5 20 47 64 89
6 34 52 68 89
8 42 52 84 94
9 49 60 84 96
32 68 73 93 98
6 is found? 1
23 is found? 0
59 is found? 0
34 is found? 1
26 is found? 0
31 is found? 0
27 is found? 0
99 is found? 0
41 is found? 0
97 is found? 0