首页 > 试题广场 >

数列还原

[编程题]数列还原

热度指数：14916 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

牛牛的作业薄上有一个长度为 n 的排列 A，这个排列包含了从1到n的n个数，但是因为一些原因，其中有一些位置（不超过 10 个）看不清了，但是牛牛记得这个数列顺序对的数量是 k，顺序对是指满足 i < j 且 A[i] < A[j] 的对数，请帮助牛牛计算出，符合这个要求的合法排列的数目。

输入描述:

每个输入包含一个测试用例。每个测试用例的第一行包含两个整数 n 和 k（1 <= n <= 100, 0 <= k <= 1000000000），接下来的 1 行，包含 n 个数字表示排列 A，其中等于0的项表示看不清的位置（不超过 10 个）。

输出描述:

输出一行表示合法的排列数目。

示例1

输入

5 5
4 0 0 2 0

输出

算法知识视频讲解

Python3

pein531

穷举

先找出缺失的数字，利用递归求取它们的全排列；然后遍历全排列的结果，将缺失数字的每一种排列填入原数组计算空值充填完之后的数组顺序对，顺序对等于k就自增计数。

def permutation(nums, p, q, candicates):
    if p == q:
        candicates.append(list(nums))
    else:
        for i in range(p, q):
            nums[i], nums[p] = nums[p], nums[i]
            permutation(nums, p + 1, q, candicates)
            nums[i], nums[p] = nums[p], nums[i]

def computePairs(nums):
    n, cnt = len(nums), 0
    for i in range(n - 1):
        for j in range(i + 1, n):
            if nums[i] < nums[j]:
                cnt += 1
    return cnt

if __name__ == "__main__":
    n, k = map(int, input().split())
    nums = list(map(int, input().split()))
    normal = [num for num in nums if num != 0]              # 未缺失数字
    missing = list(set(range(1, n + 1)) - set(normal))      # 缺失数字
    missCnt = len(missing)
    candicates = []
    permutation(missing, 0, missCnt, candicates)       # 缺失数字的全排列
    count = 0
    for candicate in candicates:
        # 把缺失数字填入原数组
        arr = list(nums)
        ptr = 0
        for i in range(n):
            if nums[i] == 0:
                arr[i] = candicate[ptr]
                ptr += 1
            else:
                arr[i] = nums[i]
        # 暴力计算顺序对
        if computePairs(arr) == k:
            count += 1
    print(count)

数据量比较小，直接暴力O(N²)计算顺序对数目就行，也可以按照归并排序的思路，用O(NlogN)的时间复杂度计算顺序对数目。

发表于 2022-01-08 16:56:30 回复(0)