python - 对列表列表中的值进行排序
问题描述
A
我有一个长度列表的列表m
。每个列表都A
包含来自 的正数{1, 2, ..., n}
。下面是一个例子,其中m = 3
和n = 4
。
A = [[1, 1, 3], [1, 2], [1, 1, 2, 4]]
我将每个数字表示x
为A
一对(i, j)
where A[i][j] = x
。我想A
按非递减顺序对数字进行排序;按最低的第一指数打破平局。也就是说, if A[i1][j1] == A[i2][j2]
, then(i1, j1)
出现在(i2, j2)
iff之前i1 <= i2
。
在示例中,我想返回这些对:
(0, 0), (0, 1), (1, 0), (2, 0), (2, 1), (1, 1), (2, 2), (0, 2), (2, 3)
表示排序后的数字
1, 1, 1, 1, 1, 2, 2, 3, 4
我所做的是一种天真的方法,其工作原理如下:
- 首先,我对中的每个列表进行排序
A
。 - 然后我迭代
{1, 2, ..., n}
列表中的数字A
并添加对。
代码:
for i in range(m):
A[i].sort()
S = []
for x in range(1, n+1):
for i in range(m):
for j in range(len(A[i])):
if A[i][j] == x:
S.append((i, j))
我认为这种方法不好。我们能做得更好吗?
解决方案
您可以制作三元组,(x, i, j)
对这些三元组进行排序,然后提取索引(i, j)
。这是有效的,因为三元组包含排序所需的所有信息,并按排序所需的顺序包含在最终列表中。(这被称为“装饰-排序-不装饰”习语,与 Schwartzian 变换有关--Hat-tip 到 @Morgen 的名称和概括以及我解释这种技术的普遍性的动机。)这可以结合起来成一个单一的声明,但为了清楚起见,我在这里将其拆分。
A = [[1, 1, 3], [1, 2], [1, 1, 2, 4]]
triplets = [(x, i, j) for i, row in enumerate(A) for j, x in enumerate(row)]
pairs = [(i, j) for x, i, j in sorted(triplets)]
print(pairs)
这是打印的结果:
[(0, 0), (0, 1), (1, 0), (2, 0), (2, 1), (1, 1), (2, 2), (0, 2), (2, 3)]
推荐阅读
- javascript - 使用 .htaccess 导航到 URL 中最后一个目录的父目录
- c++ - 为什么文件的 std::remove 总是返回-1?
- sml - SML mlb 文件中如何定义变量 SML_LIB?
- c# - 如何在 ML.NET(用于聊天机器人)中将特征化文本转换回实际文本?
- html - Flex 导致按钮超出 div
- .net - 我如何使用“GetAttribute”或“.Text”获取 StaleElementReferenceException 的值来验证硒中的 Assert.IsTrue
- reactjs - 如何更改 React 元素的属性
- javascript - 奇怪的函数语法
- javascript - 使用 jsdom 访问特定的 html 对象?
- android - Android Applink url解决冲突错误