时间戳

首页 > 解决方案 > 查找包含特定值的所有组合，其中所有值在数组中彼此相邻

algorithm - 查找包含特定值的所有组合，其中所有值在数组中彼此相邻

问题描述

我有一个包含所有唯一值的可变长度数组，我需要找到索引彼此相邻并且始终包含指定值的所有值组合。每个结果组合中的值的顺序无关紧要（但是我在示例中将它们按顺序排列以更好地说明）。

例如： [5, 4, 2, 0, 1, 3]

如果选择的具体值是 0，我们最终会得到以下 12 种组合：
0
0, 1
2, 0
0, 1, 3
2, 0, 1
4, 2, 0
2, 0, 1, 3
4, 2 , 0, 1
5, 4, 2, 0
4, 2, 0, 1, 3
5, 4, 2, 0, 1
5, 4, 2, 0, 1, 3

如果选择的具体值是 3，我们最终会得到以下 6 种组合：
3
1, 3
0, 1, 3
2, 0, 1, 3
4, 2, 0, 1, 3
5, 4, 2, 0 , 1, 3

任何编程语言的答案都可以。

编辑：我相信这可以通过找到所有数字的所有组合然后缩小该列表以确保每个组合满足要求来强制执行......它并不理想但应该可以工作。

标签： algorithmcombinations

解决方案

可以使用以下算法在 O(n^3) 时间复杂度内解决此问题：

Step-1：找到目标元素的索引。

Step-2：遍历目标的索引到最右边的索引。让我们将此迭代器称为idx。

Step-3：然后从目标索引迭代到最左边的索引。让我们将此索引称为i。

第 4 步：打印索引idx和i之间的所有元素。

按照上述步骤将打印所有组合。

上述算法的代码是使用下面的python实现的。

def solution(array,target):
    
    index = -1
    for idx,element in enumerate(array):
        if(element == target):
            index = idx
            
    n = len(array)
    
    for idx in range(n-1,index-1,-1):
        for i in range(index,-1,-1):
            for j in range(i,idx+1):
                print(array[j],end = ",")
            print()
        

arr = [5, 4, 2, 0, 1, 3]
target = 0
solution(arr,target)

推荐阅读