围绕给定位置依次排列的公共值

Question

想出了这个问题，但我不知道这是否有非暴力答案。以下问题的最佳解决方案是什么？考虑两个字符串数组，

Array1 = ['2','3','156','15','*','11','13','34','65','78']
Array2 = ['3','2','15','67','13','34','54','67','89']

找到 S1 和 S2 使得 Array1.IndexOf(S1) < Array1.IndexOf('*') < Array1.IndexOf(S2) && Array2.IndexOf(S1) < Array2.IndexOf(S2)

Answer 1

第 1 步： 将 arr1 的值在 '*' 之前索引为 1，在 '*' 之后索引为 2。

第二步：遍历arr2，首先找到索引为1的字符串，然后找到索引为2的字符串。

如果未找到对，则 S2 或两者的值将为 -1。

时间复杂度： O(n)

Space 复杂度： O(n)

arr1 = ['2','3','156','15','*','11','13','34','65','78']
arr2 = ['3','2','15','67','13','34','54','67','89']

dictionary = {}

index = 1
for string in arr1:
    if(string == '*'):
        index = 2
        continue
    dictionary[string] = index
    
    
S1 = -1
S2 = -1
for string in arr2:
    value = dictionary.get(string,-1)
    if(value == 1):
        S1 = string
    elif(S1 != -1 and value == 2):
        S2 = string
        break
        
print(S1,S2)

围绕给定位置依次排列的公共值

Common values in sequence around a given postion

algorithm

dynamic-programming

data-structures