我在面试中被问到一个问题,在 O(n) 时间内对一个二维数组进行排序。如何在 O(n) 中做到这一点。有人能解释一下吗.. 谢谢。
输入:
3 5 7 1
4 9 2 0
9 3 6 2
输出
0 1 2 2
3 3 4 5
6 7 9 9
我在面试中被问到一个问题,在 O(n) 时间内对一个二维数组进行排序。如何在 O(n) 中做到这一点。有人能解释一下吗.. 谢谢。
输入:
3 5 7 1
4 9 2 0
9 3 6 2
输出
0 1 2 2
3 3 4 5
6 7 9 9
不知道你所说的二维数组究竟是什么意思,但是有一些特定于某些情况的排序算法可以达到 O(n)。一个例子是计数排序,如果你想对一个 1 到 1000 范围内的 1000 个整数的数组进行排序,它可以在 O(n) 中排序。
编辑:它是一个多维数组这一事实不会改变排序的逻辑。您可以将索引(通过排序使用)转换为二维索引,如下所示:
array[i / N][i % N];
其中 N 是第一个维度的大小。
您可以作为普通数组进行排序。
例如
#include <stdio.h>
#include <stdlib.h>
int cmp(const void *a, const void *b){
return *(int*)a - *(int*)b;
}
#define ROW_SIZE 3
#define COL_SIZE 4
int main(void){
int M[ROW_SIZE][COL_SIZE]={{3,5,7,1},{4,9,2,0},{9,3,6,2}};
int c,r,*p;
for(p=&M[0][0],r=0;r<ROW_SIZE;++r){
for(c=0;c<COL_SIZE;++c){
printf("%d ",*p++);
}
printf("\n");
}
printf("\n");
qsort(&M[0][0], ROW_SIZE*COL_SIZE, sizeof(int), cmp);
for(p=&M[0][0],r=0;r<ROW_SIZE;++r){
for(c=0;c<COL_SIZE;++c){
printf("%d ",*p++);
}
printf("\n");
}
return 0;
}