将带有排序行的2D数组合并到一个大的1D数组中

Given a 2d array which each row is sorted from left to right, from the smallest to the biggest, I want to sort the entire array into a 1D array from the smallest to the biggest.

给定一个2d数组，每行从左到右排序，从最小到最大，我想将整个数组排序成从最小到最大的一维数组。

the number of rows is N and the number of columns is M. the complexity I need for it is MNlog(N)

行数是N，列数是M.我需要的复杂性是MNlog（N）

What I had in mind to do, is do some kind of a merge sort on the 2d array and each time send 2 rows for the function and there is the point I got stuck.

我想要做的是，在2d数组上进行某种合并排序，每次为函数发送2行，有一点我卡住了。

the signature I'm given for the function is

我为这个功能提供的签名是

void sort_rect(int a[N][M], int b[])

I'm promised the the 1d array of b has enough space for all the element of the 2d array.#C!!!

我承诺b的1d数组有足够的空间用于2d数组的所有元素。＃C !!!

3 个解决方案

#1

Using the standard approach (of merging the sorted arrays and then sorting) will give you O(NMLog(NM)).If you want an efficient approach then you should use min Heap data structure.You might want to read about heap data structure.

使用标准方法（合并排序的数组然后排序）将为您提供O（NMLog（NM））。如果您想要一种有效的方法，那么您应该使用min Heap数据结构。您可能想要阅读有关堆数据结构的信息。

Create an output array of size N*M.This will hold the output sorted array.

创建一个大小为N * M的输出数组。这将保存输出排序数组。
Create a min heap of size N.Insert first element of every sorted array.

创建一个大小为N的最小堆。插入每个已排序数组的第一个元素。
Remove the top element(minimum) from heap and put it in the output array.Replace this removed element with the next element from the same array of which this removed element was part.Repeat this until all elements are accounted for.

从堆中删除顶部元素（最小值）并将其放在输出数组中。使用此删除元素所在的同一数组中的下一个元素放置此删除元素。重复此操作直到考虑所有元素。

Complexity will be O(NMLog(N)).

复杂性将是O（NMLog（N））。

#2

Since all the elements in a[M][N] reside in sequential memory, you can treat that memory as flat. So you sort in place like this:

由于[M] [N]中的所有元素都位于顺序存储器中，因此可以将该存储器视为平坦存储器。所以你按照这样排序：

int *c = (int *)a;

and sort c, given that the size of the array is M*N.

并且排序c，假设数组的大小是M * N.

Or you can copy it to b, by defining b like this:

或者你可以将它复制到b，通过这样定义b：

int b[sizeof(a) / sizeof(int)];
memcpy(b, a, sizeof(a));

and now sort b.

现在排序b。

#3

Think of a merge sort, but applied to N arrays instead of 2. For each row you could keep an index of currently considered element. Now we need something to compare all the N values (instead of just 2). What you could do is use a heap (priority_queue) with an element structure like this:

考虑合并排序，但应用于N个数组而不是2.对于每一行，您可以保留当前被考虑的元素的索引。现在我们需要比较所有N个值（而不仅仅是2个）。你可以做的是使用一个堆（priority_queue）与这样的元素结构：

struct Element {
   int Value;
   int Row; //tells you which row in the 2d array the value comes from
}

The algorithm would be as follows:

算法如下：

You add all the values from the column 0 to the priority queue
您将列0中的所有值添加到优先级队列
Declare an array which will keep your currently considered index for each row. Initialize it to zeros.
声明一个数组，它将保留您当前考虑的每行索引。将其初始化为零。
In a loop (until you run out of elements)
- check the element on the top of the queue (element = queue.top())
- 检查队列顶部的元素（element = queue.top（））
- add element.Value to the 1d array
- 添加element.Value到1d数组
- increment currently considered index for element.Row
- 增量当前被认为是element.Row的索引
- remove the element from the top of the priority queue (queue.pop())
- 从优先级队列的顶部删除元素（queue.pop（））
在一个循环中（直到你用完元素）检查队列顶部的元素（element = queue.top（））add element.Value到1d数组增量当前被认为是element的索引。从中删除元素优先级队列的顶部（queue.pop（））

The resulting 1d array is sorted and the complexity is O(MNlog(N)). This is because you considered M*N elements and for each element adding/removing it from the priority_queue took log(N) time, because at any given moment the heap keeps no more than N elements.

得到的1d数组被排序，复杂度为O（MNlog（N））。这是因为您考虑了M * N个元素，并且对于每个元素添加/从priority_queue中删除它需要log（N）时间，因为在任何给定时刻堆都保留不超过N个元素。

I think that treating the 2d array as 1d and sorting would result in MNlog(MN) complexity which is a bit worse.

我认为将2d数组视为1d并进行排序会导致MNlog（MN）复杂度变得更糟。

#1

Create an output array of size N*M.This will hold the output sorted array.

创建一个大小为N * M的输出数组。这将保存输出排序数组。
Create a min heap of size N.Insert first element of every sorted array.

创建一个大小为N的最小堆。插入每个已排序数组的第一个元素。
Remove the top element(minimum) from heap and put it in the output array.Replace this removed element with the next element from the same array of which this removed element was part.Repeat this until all elements are accounted for.

从堆中删除顶部元素（最小值）并将其放在输出数组中。使用此删除元素所在的同一数组中的下一个元素放置此删除元素。重复此操作直到考虑所有元素。