求问英特尔9.2日笔试第3道题

def reversePairs(nums: List[Tuple[int]]):
    # 统计并记录逆序对，leetcode有原题
    def merge_sort(l, r):
        # 终止条件
        if l >= r: return 0
        # 递归划分
        m = (l + r) // 2
        res = merge_sort(l, m) + merge_sort(m + 1, r)
        # 合并阶段
        i, j = l, m + 1
        tmp[l:r + 1] = nums[l:r + 1]
        for k in range(l, r + 1):
            if i == m + 1:
                nums[k] = tmp[j]
                j += 1
            elif j == r + 1 or tmp[i][0] <= tmp[j][0]:
                nums[k] = tmp[i]
                i += 1
            else:
                for p in range(i, m + 1):
                    reverse_pairs[tmp[p]].append(tmp[j])
                nums[k] = tmp[j]
                j += 1
                res += m - i + 1  # 统计逆序对
        return res

    from collections import defaultdict
    reverse_pairs = defaultdict(list)
    tmp = [tuple()] * len(nums)
    merge_sort(0, len(nums) - 1)
    return reverse_pairs


def can_sort_by_one_move(nums):
    # 使用<逆序数对>来确定能否一步排序
    # 判据：设数组的逆序数对如下：[(xi, xj)], i,j=1,...,N. 称xi为逆序头，xj为逆序尾，并把逆序对看作是父子关系。
    # 则对每一个逆序头xi，若其孩子和其他逆序头一样，则说明可以一步排序
    # 例：nums = [3,4,1,2] 逆序对：[(3,1),(3,2),(4,1),(4,2)]
    # 因 3 的逆序孩子和 4 的逆序孩子相同，即 {3:[1,2], 4:[1,2]}
    # 所以可以一次排序：可以通过移动数组某一连续部分，使得数组有序
    def helper(nums):
        # 为了避免重复元素的扰乱，为每个数组元素分配id，最终数组变成[(x0,0), (x1,1), ..., (xn,n)]
        ipt = [(a, b) for a, b in zip(nums, range(len(nums)))]
        x = reversePairs(ipt)
        y = list(x.values())
        # 若逆序数为0，或每个逆序头的孩子相同，则可一步排序
        return len(y) == 0 or y.count(y[0]) == len(y)

    return helper(nums) or helper(list(reversed(nums)))


# 测试
a = [3, 4, 4, 5, -2, -1]  # True
b = [1, 3, 5, 2, 4, 6]  # False
c = [1, 2, 3, 4, 5, 6, 7]  # True
d = [3, 4, 5, 6, 7, 1, 2]  # True
e = [5, 6, 7, 3, 4, 1, 2]  # False
f = [1, 2, 5, 6, 7, 3, 4]  # True
h = [3, 4, 1, 2, 5, 6, 7]  # True
i = [5, 6, 7, 1, 2, 3, 4]  # True
j = [7, 6, 5, 2, 1, 4, 3]  # True
l = (a, b, c, d, e, f, h, i, j)
for k in l:
    print(can_sort_by_one_move(k))