将一个二维数组转换为两个一维数组

Question

您可能会对我所提出的问题感到奇怪，但事实如此：将1个二维数组转换为2个一维数组。这是我的老师问的问题，他说谁回答正确就可以得到完美的分数（我觉得这个问题很棘手）。我可以把任何2或n维数组转化为一个一维数组，但他只要求2维，所以我认为第二个数组必须有些特殊之处。而且，他没有说明数组的类型（int、String还是object），所以我认为它必须适用于任何类型的二维数组。

如果这里没有人弄清楚他想要什么，那么这就是我将向他回答的内容：将其转换为一个一维数组，并使第二个数组为空（或不包含任何元素）。但我认为对于这样一个棘手的问题来说，这不是一个好答案。

编辑：以下是我的老师的问题，逐字逐句（他只是在声音结束时作为奖励问题询问，没有出现在教材中，附有一个不错的奖励）：给定一个二维数组，将其转换为两个一维数组。

我不知道 Java 和 C# 中的 [][] 是否被认为是二维数组，但 C# 确实有 [, ]，它是二维数组。我们正在学习计算机算法，没有目标 IDE 或语言。

编辑2：我给他发了电子邮件，他拒绝提供更多信息（他说如果我比其他人知道更多信息，这是不公平的），他也没有对交错数组的想法进行任何评论。他回信唯一有用的东西是让 [][] 被认为是二维数组。

- Luke Vo

---

鉴于Java实际上并没有真正的二维数组（它拥有数组的数组），因此很难给出一个好的答案。最好提供一个明确的问题，并附带样例输入和期望输出。我认为问题不是“棘手”，而是“规格不够明确”。 - Jon Skeet

这更像是一个横向思维谜题，而不是编程问题。也就是说，他使用了什么技巧，在给你一些额外信息后，使他所说的有意义。 - George Duckett

你能发布（或链接到）导师问题的确切措辞吗？ - 01d55

如果您的老师下次提出更多细节，那么恐怕这个问题的措辞太差了，无法得出有意义的明确答案。请向您的老师追问更多细节。 - Jon Skeet

一个想法是在一个数组中按行存储，在第二列中按列存储，一些能够进行两次遍历的图像算法（首先水平遍历，然后垂直遍历）可能会从中受益。我认为这比保存行起始索引更合理的解释，因为你可以很容易地计算它们。 - Giedrius

Answer 1

我来翻译一下：可以通过一致地读取和写入将整个二维数组压缩为两个一维数组中的第一个数组。即按顺序在该第一个数组中存储第1行，然后是第2行等等。每当移动到下一行时，在第二个一维数组中存储下一个单元格（第一个一维数组的索引），这基本上将成为一个行索引表。正如Jon Skeet所说，这不是一个非常明确的问题；也许有了更明确的信息，我们才能更好地帮助您。

- JNadal

---

值得注意的是，对于二维数组来说，第二个数组并不是必需的（因为行长度是恒定的），但对于锯齿形数组来说则是必需的。 - George Duckett

你不需要行索引的数组，因为可以为二维数组计算它（它不是锯齿状的）。 - Rune FS

正如George所说，如果你的数组看起来像这样：{1,2,3,4}，{1,2}，{1,2,3,4,5}，并且适合一个3x5的数组中，那么你需要存储索引。 - JNadal

我还在等待更多的答案和评论。如果接下来的两天没有更好的答案，我会将其标记为答案。对于这次延迟我感到抱歉 :) - Luke Vo

抱歉伙计。答案是巴伯的想法。不过，我还是得到了一个完美的分数，因为他给了我第二次机会！非常感谢！ - Luke Vo

Answer 2

如果我正确理解了您的问题，那么这很简单...

这只是一个算法问题，而不是针对某种编程语言的特定问题...

您可以像这样做：

1. one array holds the values
2. second array holds the keys

3. try to find a workaround in the second array to know what keys you've got..

   For example:
   array_1: v0 v1 v2 null v3 v4 v5 null v6 v7 v8 null
   array_2: 0  1  2  newR 0  1  2  newR 0  1  2  newR
   

你也可以将它表示为一个数组...但你需要一个特定的算法来确定你位于矩阵的Y位置。

问题在于你无法立刻从内存中访问数据，这就是为什么有二维数组存在的原因。

另一种方法：

1. keep in array 1 the values

2. keep in the second array the keys as string like in the following example:

   array1: value1 value2 value3 value4 value5
   array2: 0,0    0,1    1,0    1,1    2,0
   

有很多算法，但我认为你不会找到比二维数组更好的...

当你查找它们时，性能会降低...当然...除非你将它们保留在哈希表中...将0,0哈希化并作为键添加到哈希表中，并将指定值添加到该键中。然后你可以搜索键“0,0”...

- Alex

Answer 3

我猜你想把你的二维数组（类型为RelevantType[,]）转换成两个数组（类型为SomeTypeA[]和SomeTypeB[]），而不会丢失任何信息？

这并不是很难： 将第一个数组的类型设置为RelevantType[]，第二个数组的类型设置为int[]，将你的二维数组内容复制到第一个数组中，并将其第一个索引复制到第二个数组中，就完成了。

- Falanwe

---

他没有提到数组类型，所以我猜我必须将 someType[, ] 转换为 2 个 someType[]，而且，你说对了一件事：没有信息丢失。 - Luke Vo

Answer 4

将二维数组按行优先或列优先方式展开，存储到其中一个一维数组中。将数组的形状{n, m} 存储在另一个一维整型数组中。给定值的二维数组元素的索引，您可以使用该形状来计算值的一维数组中的索引。

这两种表示是同构的，都允许常量时间内查找值。它也类似于如何在内存中表示二维数组。

- Michael J. Barber

---

不客气！如果您编写了任何代码来演示这种方法，我希望您会将其编辑到问题中，以供未来任何人查看。 - Michael J. Barber