1

假设我们有一个长度为 N 的对象数组（所有对象都具有相同的字段集）。

我们有一个长度为 N 的相同类型值的数组，它们代表某个对象的字段（例如，代表 ID 的数字数组）。

现在我们要按在第二个数组中表示的字段对对象数组进行排序，并且与第二个数组中的顺序相同。

例如，这里有 2 个数组（如描述）和预期结果：

A = [ {id: 1, color: "red"}, {id: 2, color: "green"}, {id: 3, color: "blue"} ]
B = [ "green", "blue", "red"]

sortByColorByExample(A, B) == 
    [ {id: 2, color: "green"}, {id: 3, color: "blue"}, {id: 1, color: "red"} ]

如何有效实现“逐例排序”功能？那我想不出更好的了O(N^2)。

4

5 回答 5

3

B这是假设你有一个从元素到元素的双射A

M从B的元素到它们的位置 ( O(N))构建一个地图（比如）

对于A( O(N)) 的每个元素，访问映射以查找将其放在排序数组中的位置（O(log(N))使用映射的有效实现）

总复杂性：O(NlogN)时间和O(N)空间

于 2013-01-11T13:18:55.473 回答
2

假设我们正在对物品的颜色进行分类。然后创建一个字典d，将每种颜色映射到 A 中具有该颜色的项目列表。然后遍历列表 B 中的颜色，并为每个颜色c从列表d [ c ]中输出（并删除）一个值。这在 O( n ) 时间内运行，为字典提供 O( n ) 额外空间。

请注意，如果无法根据 B 中的示例对 A 进行排序，您必须决定该怎么做：您会引发错误吗？选择最大化匹配数的顺序？要不然是啥？

无论如何，这是 Python 中的一个快速实现：

from collections import defaultdict

def sorted_by_example(A, B, key):
    """Return a list consisting of the elements from the sequence A in the
    order given by the sequence B. The function key takes an element
    of A and returns the value that is used to match elements from B.
    If A cannot be sorted by example, raise IndexError.

    """
    d = defaultdict(list)
    for a in A:
        d[key(a)].append(a)
    return [d[b].pop() for b in B]

>>> A = [{'id': 1, 'color': 'red'}, {'id': 2, 'color': 'green'}, {'id': 3, 'color': 'blue'}]
>>> B = ['green', 'blue', 'red']
>>> from operator import itemgetter
>>> sorted_by_example(A, B, itemgetter('color'))
[{'color': 'green', 'id': 2}, {'color': 'blue', 'id': 3}, {'color': 'red', 'id': 1}]

请注意，此方法处理序列 B 中有多个相同值的情况，例如：

>>> A = 'proper copper coffee pot'.split()
>>> B = 'ccpp'
>>> ' '.join(sorted_by_example(A, B, itemgetter(0)))
'coffee copper pot proper'

在这里，当 中有多个相同的值时B，我们以相反的顺序获取对应的元素A，但这只是实现的产物：通过使用 acollections.deque代替列表（而popleft不是pop），我们可以安排获取相应的元素的A原始顺序，如果这是首选的话。

于 2013-01-11T13:23:01.207 回答
0

制作一个数组数组，称其为大小为 B.length 的 C。遍历 A。如果它的颜色为“绿色”，则将其放入 C[0]。如果它的颜色为“蓝色”，则将其放入 C[1]，如果它的颜色为红色，则将其放入 C[2]。完成后，通过 C 并将其展平为原始结构。

于 2013-01-11T13:11:17.440 回答
0

类似于合并排序的东西不是更好吗？创建 B.length 数组，为 B 中的每个元素创建一个数组，然后遍历 A，并将它们放置在适当的较小数组中，然后在完成后将数组合并在一起。它应该在 O(2n) 左右

于 2013-01-11T13:17:02.493 回答
0
  • 遍历第一个数组并创建一个HashMap这样的字段而不是List对象。O(n) [假设这些关键字段的值重复]

例如。key = green 将包含字段值为 Green 的所有对象

  • 现在遍历第二个数组，从 HashMap 中获取对象列表并将其存储在另一个数组中。O(k) ..（其中 k - 字段的不同值）

总运行时间为 O(n)，但它需要一些额外的内存，例如映射和辅助数组

最后，您将根据您的要求对数组进行排序。

于 2013-01-11T13:19:28.017 回答