Interview Question
Country: United States
#define INT_MAX 2147483647
void PrintMatrix(int *Matrix, int M, int N)
{
int *ArrIndexes = new int[N];
for(int i = 0; i < N; i++)
{
ArrIndexes[i] = 0;
}
for(int i = 0; i < M*N; ++i)
{
int Min = INT_MAX;
int MinArray = 0;
for(int j = 0; j < N; j++)
{
int *arr = &Matrix[j*M];
if(ArrIndexes[j] < M)
{
if(arr[ ArrIndexes[j] ] < Min)
{
Min = arr[ ArrIndexes[j] ];
MinArray = j;
}
}
}
TRACE("%d", Min);
if(i != M*N-1)
{
TRACE(", ");
}
ArrIndexes[MinArray]++;
}
}
void main()
{
int Matrix[3][3] = { {20, 40, 80}, {5, 60, 90}, {45, 50, 55} };
PrintMatrix((int *)Matrix, 3, 3);
}
merge sort.
n,m stand for height and width of the matrix.
time: O(n*m*logn)
space: O(n * m) space for auxiliary array
#include <cstdio>
#define N 3
#define M 3
int aux[N * M];
int matirix[N][M] = {{20, 35, 900}, {5, 40, 45}, {50, 60, 75}};
void merge_sort(int l, int h, int * array) {
if (l >= h)
return;
/* (l + h) / 2 might overflow */
int m = l + (h - 1) / 2;
int i = 0;
int j = 0;
int k = 0;
merge_sort(l, m, array);
merge_sort(m + 1, h, array);
while(i < (m - l + 1) * M && j < (h - m) * M) {
if (array[l * M + i] <= array[(m + 1) * M + j]) {
aux[k++] = array[l * M + i++];
} else {
aux[k++] = array[(m + 1) * M + j++];
}
}
while (i < (m - l + 1) * M)
aux[k++] = array[l * M + i++];
while (j < (h - m) * M)
aux[k++] = array[(m + 1) * M + j++];
for (i = 0; i < k; ++i) {
array[l * M + i] = aux[i];
}
}
int main(int argc, char const *argv[]) {
merge_sort(0, N - 1, (int *)matirix);
for (int i = 0; i < N; ++i)
for (int j = 0; j < M; ++j){
printf ("%d", matirix[i][j]);
if ((i+1) * (j + 1) < N * M)
putc(',', stdout);
}
putc('\n', stdout);
return 0;
}
}
Similar to merging multiple sorted arrays
- Anonymous March 08, 2015