题目
排列41253的逆序数是_____________.
排列41253的逆序数是_____________.
题目解答
答案
4
解析
逆序数是指排列中所有逆序对的总数,其中逆序对的定义是较大的数排在较小数前面。计算时,需要依次检查每个元素右侧比它小的元素个数,最后将所有结果相加。
关键步骤:
- 从左到右逐个元素分析;
- 对每个元素,统计其右侧比它小的元素个数;
- 将所有统计结果求和。
排列为 $41253$,逐个元素分析:
- 元素 $4$:右侧有 $1,2,5,3$,其中比 $4$ 小的有 $1,2,3$,共 $3$ 个逆序对;
- 元素 $1$:右侧有 $2,5,3$,均比 $1$ 大,无逆序对;
- 元素 $2$:右侧有 $5,3$,均比 $2$ 大,无逆序对;
- 元素 $5$:右侧有 $3$,比 $5$ 小,共 $1$ 个逆序对;
- 元素 $3$:无右侧元素,无逆序对。
总逆序数为 $3 + 0 + 0 + 1 + 0 = 4$。