213小R的排列挑战

题解

小 R 有一个长度为 n 的排列，排列中的数字是 1 到 n 的整数。她每次操作可以选择两个数a_i和a_j进行交换，前提是这两个数的下标 i 和 j 的奇偶性相同（即同为奇数或同为偶数）。目标是通过最少的操作使数组变成升序排列，如果无法实现则输出-1。

思路

1. 下标分组：将数组根据下标的奇偶性分为两部分：

   • 奇数下标元素（0-based，即索引为 0,2,4,…）
   • 偶数下标元素（索引为 1,3,5,…）

2. 排序验证：

   • 奇数下标的元素在最终的升序排列中应该是奇数序列，即1,3,5,...。
   • 如果奇数下标的排序结果不符合预期，则无法通过交换操作将数组排序，返回-1。

3. 逆序数计算：

   • 分别计算奇数下标和偶数下标部分的逆序数。
   • 逆序数代表需要多少次交换才能使该部分有序。
   • 总交换次数为奇数下标和偶数下标部分的逆序数之和。

代码实现

# from bisect import bisect_right
# class BIT:
#     def __init__(self, n):
#         self.tree = [0] * n  # 注意下标从1开始

#     def lowbit(self, x):
#         return x & (-x)

#     # arr[i] += val
#     def update(self, i, val):
#         while i < len(self.tree):
#             self.tree[i] += val
#             i += self.lowbit(i)

#     # 返回arr[:i+1]的sum
#     def query(self, i):
#         res = 0
#         while i > 0:
#             res += self.tree[i]
#             i -= self.lowbit(i)
#         return res
# 树状数组求解逆序对，时间复杂度为nlogn
# def inv(a):
#     n = len(a)
#     res = 0
#     tree = BIT(n + 1)
#     b = sorted(a)
#     for x in a:
#         i = bisect_right(b, x)
#         res += tree.query(n) - tree.query(i)
#         tree.update(i, 1)
#     return res

# 暴力求解逆序对，时间复杂度为n²
def inv(a):
    n = len(a)
    res = 0
    for i in range(n):
        for j in range(i + 1, n):
            if a[i] > a[j]:
                res += 1
    return res


def solution(n: int, a: list) -> int:
    odd, even = [], []
    for i in range(n):
        if i % 2 == 0:
            odd.append(a[i])
        else:
            even.append(a[i])
    if sorted(odd) != list(range(1, n + 1, 2)):
        return -1
    return inv(odd) + inv(even)


if __name__ == '__main__':
    print(solution(5, [1, 4, 5, 2, 3]) == 2)
    print(solution(4, [4, 3, 2, 1]) == -1)
    print(solution(6, [2, 4, 6, 1, 3, 5]) == -1)

复杂度分析

• 时间复杂度：O(n²)，主要由逆序数的双重循环计算决定。(可以用树状数组求解逆序对，时间复杂度为 O(nlogn))
• 空间复杂度：O(n)，用于存储奇数和偶数下标的元素。