大小为n的置换是n个整数的序列,其中从1到n的每个值恰好出现一次。例如,序列[3,1,2]、[1]和[1,2,3,4]是排列,而[2]、[4,1,2]、[3,1]不是排列。
所以我收到2个输入:1 -排列中的数,2 -本身的排列。
问题是:有多少间隔[l,r](1 ≤ l ≤ r ≤ n),其中序列p[l.. r]也是一个置换?举例来说:
input - 7; [6, 3, 4, 1, 2, 7, 5]
The answer is 4:
permutation is [6, 3, 4, 1, 2, 7, 5];
permutation is [1];
permutation is [1, 2];
permutation is [3, 4, 1, 2]
希望你能理解这个问题。
我写了前两个案例,但我不知道如何检查其他案例:
numbers = int(input("Amount of elements in permutation: "))
perm = list(input("Permutation: "))
perm = [ int(x) for x in perm if x != " "]
amount = 1
first = 1
if len(perm) == numbers and int(max(perm)) == numbers and int(min(perm)) == 1:
if first in perm and len(perm) > 1:
amount += 1
3条答案
按热度按时间polhcujo1#
实际上只是尝试了一个例子,如果有一个错误请告诉我。
scyqe7ek2#
时间复杂度为O(n)。
初始化以下内容:
重复执行以下操作:
思想:我们总是添加最小的邻居,因为它必须包含在任何包含较大邻居的排列中。如果我们考虑的元素总数等于我们看到的最大元素,那么我们必须有从1到最大元素的所有元素,所以我们找到了另一个排列。
示例:[6、3、4、1、2、7、5]
将按此顺序考虑置换候选项
这是线性时间,恒定的记忆。
7kqas0il3#
在R中,可以像下面这样使用
embed
或使用
for
循环你将获得
和