如何在Python中获取连续重复值最少的指定长度整数子序列

问题说明 #

给定整数列表：

A = [7, 3, 7, 3, 1, 3, 4, 1]

数字与地点的对应关系：

• 7 = USA
• 3 = UAE
• 1 = India
• 4 = Pakistan

需求：找出连续的k个地点（初始k=5），使得子序列中重复出现的地点类型数量最少；同时支持动态调整k的取值。

实现方案 #

采用滑动窗口法遍历所有长度为k的连续子数组，实时统计窗口内重复出现的地点类型数量，最终筛选出符合要求的子序列。该方法时间复杂度为O(n)（n为原数组长度），效率较高。

代码实现 #

def find_min_dup_type_subarray(arr, k):
    n = len(arr)
    if k > n:
        return None  # k大于数组长度时无符合条件的子数组
    
    min_dup_types = float('inf')
    result_subarrays = []
    
    # 初始化滑动窗口的元素计数与重复类型数
    count = {}
    dup_types = 0
    for i in range(k):
        num = arr[i]
        prev_count = count.get(num, 0)
        count[num] = prev_count + 1
        # 元素从1次变为2次时，重复类型数+1
        if prev_count == 1:
            dup_types += 1
    
    min_dup_types = dup_types
    result_subarrays.append(arr[:k])
    
    # 滑动窗口遍历剩余元素
    for i in range(k, n):
        # 移除窗口左端元素
        left_num = arr[i - k]
        left_prev_count = count[left_num]
        count[left_num] -= 1
        # 元素从2次变为1次时，重复类型数-1
        if left_prev_count == 2:
            dup_types -= 1
        if count[left_num] == 0:
            del count[left_num]
        
        # 添加窗口右端元素
        right_num = arr[i]
        right_prev_count = count.get(right_num, 0)
        count[right_num] = right_prev_count + 1
        # 元素从1次变为2次时，重复类型数+1
        if right_prev_count == 1:
            dup_types += 1
        
        # 更新结果
        if dup_types < min_dup_types:
            min_dup_types = dup_types
            result_subarrays = [arr[i - k + 1:i + 1]]
        elif dup_types == min_dup_types:
            result_subarrays.append(arr[i - k + 1:i + 1])
    
    return result_subarrays, min_dup_types

# 示例使用
A = [7, 3, 7, 3, 1, 3, 4, 1]
name_map = {7: 'USA', 3: 'UAE', 1: 'India', 4: 'Pakistan'}

# k=5的情况
k = 5
subarrays, min_dup = find_min_dup_type_subarray(A, k)
print(f"当k={k}时，重复地点类型最少的子序列：")
for sub in subarrays:
    named_sub = [name_map[num] for num in sub]
    print(f"数字序列：{sub}，对应地点：{named_sub}，重复的地点类型数：{min_dup}")

# 动态调整k为4的情况
k = 4
subarrays, min_dup = find_min_dup_type_subarray(A, k)
print(f"\n当k={k}时，重复地点类型最少的子序列：")
for sub in subarrays:
    named_sub = [name_map[num] for num in sub]
    print(f"数字序列：{sub}，对应地点：{named_sub}，重复的地点类型数：{min_dup}")

代码说明 #

• 函数find_min_dup_type_subarray接收原数组和子数组长度k作为参数，返回所有重复地点类型最少的子序列，以及对应的重复类型数量。
• 滑动窗口机制避免了重复统计子数组元素，保证了效率。
• 支持动态修改k的值，只要k不超过原数组长度即可正常运行。

示例输出 #

运行代码后，k=5的输出如下：

当k=5时，重复地点类型最少的子序列：
数字序列：[7, 3, 1, 3, 4]，对应地点：['USA', 'UAE', 'India', 'UAE', 'Pakistan']，重复的地点类型数：1
数字序列：[3, 1, 3, 4, 1]，对应地点：['UAE', 'India', 'UAE', 'Pakistan', 'India']，重复的地点类型数：1

其中[7,3,1,3,4]就是题目中提到的示例子序列，仅存在1种重复地点（UAE）。

内容的提问来源于stack exchange，提问作者azhar