4109.统计有效后缀排序的数量II
难度:困难
问题描述:
给你两个整数数组nums和target,长度分别为n和m,其中n<=m。
对于每个下标i,考虑将原数组的后缀nums[i..n-1]按非递增顺序排序。
返回一个长度为m-n+1的整数数组ans,其中ans[k]表示使排序后的数组等于target[k..k+n-1]的下标i的数量。
子数组是数组中一个连续的非空元素序列。
数组的后缀是从任意下标开始并延伸至数组末尾的子数组。
示例1:
输入:nums=[2,2,3],target=[2,2,3,2,1,3,2,2]
输出:[1,1,0,0,0,1]
解释:
分别对从下标0、1和2开始的后缀排序,会依次得到[3,2,2]、[2,3,2]和[2,2,3]。
k=0:选择i=2可以得到[2,2,3]。
k=1:选择i=1可以得到[2,3,2]。
k=2,3,4:均无法得到对应的子数组。
k=5:选择i=0可以得到[3,2,2]。
因此,答案为[1,1,0,0,0,1]。
示例2:
输入:nums=[5,6,5],target=[5,6,5,5,6,5]
输出:[2,1,0,2]
解释:
对从下标0开始的后缀排序,会得到[6,5,5];对从下标1或2开始的后缀排序,都会得到[5,6,5]。
k=0:选择i=1或i=2可以得到[5,6,5]。
k=1:选择i=0可以得到[6,5,5]。
k=2:无法得到[5,5,6]。
k=3:选择i=1或i=2可以得到[5,6,5]。
因此,答案为[2,1,0,2]。
提示:
n==nums.length
m==target.length
1<=n<=m<=10**5
1<=nums[i],target[i]<=10**5
问题分析:
解决分为下列步骤,一是对nums的每一个索引i将其后缀按非递增排序之后得到的序列求出并返回,这通过子函数 get_non_increasing_order_postfix_from_every_index(nums)实现,二是对target中的每一个k截取子数组,统计这个子数组在按后缀排序得到的序列中出现的个数,存入列表并返回,这通过子函数def get_number_of_valid_suffix_sorts(t,target)实现,最后在主程序中输出这个列表即是问题的解。
程序如下:
#对nums的每一个i将后缀按非递增排序之后得到的序列求出并返回
def get_non_increasing_order_postfix_from_every_index(nums):
n=len(nums)
t=[]
for i in range(n):
a=nums[:i]
b=nums[i:]
b.sort(reverse=True)
t.append(a+b)
return t
#统计有效后缀排序的数量列表并返回
def get_number_of_valid_suffix_sorts(t,target):
n=len(t[0])
ans=[]
m=len(target)
for k in range(m-n+1):
a=target[k:k+n]
c=t.count(a)
ans.append(c)
return ans
#主程序
nums=eval(input('pls input nums='))
target=eval(input('pls input target='))
t=get_non_increasing_order_postfix_from_every_index(nums)
a=get_number_of_valid_suffix_sorts(t,target)
print(a)
运行实例一
pls input nums=[2,3,2,4]
pls input target=[2,3,2,4,3,2,4,1]
[1, 0, 1, 0, 0]
运行实例二
pls input nums=[2,3,4]
pls input target=[4,3,2,3,4,2,4,3]
[1, 0, 1, 0, 0, 1]
转载自 CSDN-专业IT技术社区
原文链接:https://blog.csdn.net/2302_79682652/article/details/170435847




