题目
排列165342的逆序数是()A.8B.9C.7D.6
排列165342的逆序数是()
A.8
B.9
C.7
D.6
题目解答
答案
首先，我们将排列 165342 分解为单个数字的列表： [1, 6, 5, 3, 4, 2]
然后，我们从左到右遍历这个列表，并对每个数字检查其后面的数字。如果当前数字大于其后面的数字，那么这两个数字就构成一个逆序数。
1. 1 ：没有比 1 小的数字。
2. 6 ：比 6 小的数字有 5, 3, 4, 2 ，共 4 对。
3. 5 ：比 5 小的数字有 3, 4, 2 ，共 3 对。
4. 3 ：比 3 小的数字有 2 ，共 1 对。
5. 4 ：比 4 小的数字有 2 ，共 1 对。
6. 2 ：没有比 2 小的数字。
总共有 4 + 3 + 1 + 1 = 9 对逆序数。
答案是 B.9。
解析
逆序数是指排列中前面的数大于后面的数的情况的总数。解题的核心思路是逐个元素检查其右侧比它小的元素个数，最后累加所有结果。关键在于：
- 从左到右遍历每个元素；
- 对每个元素，统计其右侧比它小的元素数量；
- 将所有结果相加。
将排列 165342 分解为数字列表：[1, 6, 5, 3, 4, 2]，逐个元素分析：
- 元素
1：右侧无更小元素，贡献0； - 元素
6：右侧有5, 3, 4, 2，共4个更小元素； - 元素
5：右侧有3, 4, 2，共3个更小元素； - 元素
3：右侧有2，共1个更小元素； - 元素
4：右侧有2，共1个更小元素； - 元素
2：右侧无更小元素，贡献0。
总逆序数为：4 + 3 + 1 + 1 = 9。