1

给定一个 n*n 元素的二维数组：

  • 所有行都已排序
  • 所有列都已排序

例如：

1 5 7
2 6 8
3 9 10

将其转换为一维排序数组。有没有比O(nlog(n)).

4

6 回答 6

2

嗯，它不能低于n^2复杂性，因为你有一些n^2元素，你必须每个元素至少检查一次。

执行此操作的算法是标准的 k 路合并，其复杂度为N log k，其中N是要合并的项目总数，k是序列数。

在您的n*n数组中，您有n*n要合并的项目和n序列（即行）。因此，代入上述等式：

N log k
N = (n*n)
k = n
(n*n) log n

将您的 2D 数组转换为已排序的 1D 数组是n^2 log n.

于 2014-07-24T19:21:27.597 回答
0

我认为这将是我将采取的方法：

1）从第一行开始 - “1 5 7”。我们知道，在开始时，行是排序的，所以我们保证最左边的元素是最少的，不需要比较。输出 1，并将第一列向上移动，得到“2 5 7”。

2) 现在比较前两个元素。只要第一个元素小于第二个元素，就继续输出第一个元素并将其各自的列向上移动。这给了我们 2 和 3 的输出，结果数组是“5 7”（因为第一列现在是空的）。

3) 对剩下的两列继续做同样的事情。这将为我们提供 5 和 6 的输出，然后我们会遇到第一种不同的情况——此时我们的数组将包含“9 7”。

4) 在这种情况下，我们将输出最后一列的值并将其上移，在输出 7 后给出“9 8”。我们再次遇到第一个元素更大的情况，因此我们将输出第二个并将该列向上移动，留下“9 10”。

还没有彻底分析它，但我认为这是 O(N)，因为您可以对各个列之间的关系做出假设，因此最多有 N 次比较。

于 2014-07-24T20:25:50.103 回答
0

你可以在 O(n) 中做到这一点。我不同意这不可能比 n^2 更快，因为在这种情况下 n*n=n 因为当您谈论时间复杂度时，您指的是列表中元素的数量。这是 O(n) 解决方案，其中 n = min-max。为此，您需要知道可能在列表中的最小数字和最大数字。你不需要知道它们只是最低和最高的可能。

    int[] Sorted1dArray(int[][] arr, int min, int max)//basically counting sort
    {
       int index = 0;
       int rowColSize = arr[0].Length;
       int[] newArr = new int[max-min];
       int[] ret = new int[rowColSize *rowColSize ];
       for(int i=0;i<rowColSize ;i++)//
       {
          for(int j=0;j<rowColSize ;j++)
             newArr[arr[i][j]]++;
       }
       for(int i=0;i<newArr.Length;i++)
       {
          for(int j=0;j<newArr[i];j++)
          {
             ret[index++]=newArr[j];
          }
       }
       return ret;
    }
于 2014-07-24T17:59:24.053 回答
0

我有时间：O(n*n log(2n)) 空间 O(2n) 算法。

基本思路如下

a[0][0] 肯定是最小的元素。因为元素是按行和按列排序的，所以下一个最小的元素将是 min( a[0][1], a[1][0] )。比如说，a[0][1] 是两者中最小的，下一个候选者将是 min(a[0][2],a[1][1],a[1][0])

等等，

算法：

选择最小的候选元素，打印它。将元素推到最小元素的右侧和底部作为潜在候选者。（检查 out 或 bound。）这样做直到没有更多的候选元素存在。

需要 DS：

候选元素可以使用堆来维护（顶部是最小元素）但是你需要确保你不要两次推送相同的元素。（y 可能在 x 的右侧和 z 的底部）。在你推送到堆之前，你需要知道元素是否已经被推送。

这两个要求都由 set 优雅地处理（这是有序的）（我在 c++ 中编写代码）

在集合中存储索引将使我能够轻松地将下一个候选元素推送到候选 Ds。
在我的候选 ds 中，我在任何时间点都保持不超过 n+n 个元素以下是我使用的比较函数。

bool operator()(const int& a,const int& b) const{
        int ai=a/m,aj=a%m;
        int bi=b/m,bj=b%m;
        if(input[ai][aj]!=input[bi][bj])
        return input[ai][aj]<input[bi][bj];
        else
        return a<b;
    }

示例实现在这里：http: //ideone.com/w208Af

于 2013-11-27T18:58:06.067 回答
0

您应该发布您的O(n log n)解决方案：事实是，没有这样的解决方案真的是可能的。这就是为什么。你有n*n元素。所以你能做的最好的就是n^2你必须至少访问每个元素一次。考虑一下。您必须填充一个长度为一维数组n*n（即二维数组的每个元素都必须存在于新的一维数组中）。因此，您无法在O(n log n).

于 2012-11-18T22:50:51.977 回答
0

您可以使用函数 f(x,y) = (f(x),f(y)) 来降低复杂性并展平二维数组。它还对一维数组重新排序。因为它是一个函数，它更像是一个散列算法，也许不是你想要的？

于 2012-09-18T19:17:20.113 回答