查找两个最大且不连续的值的索引

Question

给定以下向量，

a = [0, 11, 22, 10, 5, 6, 7, 8, 9, 23, 25, 18, 10]

我需要识别"a“的索引，它的元素是两个最大的不连续的值，如下所示：

idx = [2, 10] 

(a2 = 22；a10 = 25)。

此外，可以设置这些查找数之间的最小距离间隔(my_gap)；例如在跟随矢量中，

a = [10, 11, 14, 28, 10, 30, 8, 11, 13, 11, 28, 10]

我希望有：idx= [5, 10]，因为我希望最大值之间的位置至少为3。在本例中，第一个'28‘与'30’太接近(它们相差5-2=3个位置，另一个'28‘离'30’-->abs(5-10) =5>my_gap更远)。

为了更准确地避免误解，有没有什么pythonic方法可以重写下面的代码？谢谢

import numpy as np

a = [60, 2, 3, 21, 18, 22, 0, 70, 118, 111, 100, 120, 10, 6]
idx = np.argsort(a)[::-1]
a_sorted = np.sort(a)[::-1]
n_gap = 3

first_value = a_sorted[0]
second_value = []
for i in range(1, len(idx)):
    if abs(idx[0] - idx[i]) > n_gap:
        second_value = a_sorted[i]
        break
print('first value: ', first_value)
print('second value: ', second_value)

Answer 1

我会用max()和index()函数尝试一下。首先，从列表中获取索引和最大值，然后使用remove()从my_gap中删除所需的值，然后再次执行max()搜索。像这样的东西：

max_value = a.max()
max_index = a.index(max_value)
my_gap = 5

for i,j in enumerate(a):
  if i > max_index - my_gap and i < max_index + my_gap:
     a.remove(i)

max_value2 = a.max()
max_index2 = a.index(max_value)

请记住，最好在删除内容之前创建列表的副本。

Answer 2

线性复杂度版本。

大致O(N)时间和常量空间

它的工作原理是建立一个最大值列表，直到每个索引，

然后检查每个元素和直到(当前元素的索引- k)的最大值，

这是因为最大值(这个index - k)将是当前元素的最佳配对，并且最大配对必须包含列表的最大值。

a = ([0, 11, 22, 10, 5, 6, 7, 8, 9, 23, 25, 18, 10],
     [10, 11, 14, 28, 10, 30, 8, 11, 13, 11, 28, 10],
     [20, 21, 19, 18, 17],
     [10,8,9,11,12],
     [0, 0, 0, 10, 15, 16, 15, 0, 0, 0, 11,13,15,12,10],
     [60, 2, 3, 21, 18, 22, 0, 70, 118, 111, 100, 120, 10, 6])

n_gap = 3 #minimum distance

k = n_gap + 1 # k is position offset, which is 1 more than gap size
for a in a:
    if(len(a) <= k): # not enough elements for gap size
        print('no answer')
        continue
    m = a[0]
    mi = 0
    maxes = (m, a[k], mi, k)
    for i,x in enumerate(a):
        if x > m:                         #new maximum found
            if i >= k:                      #index big enough to have a pair
                mit, mt = a[i - k]             #get incremental maximum at gap
                maxes = (x, mt, i, mit)     #init maxes with max pair candidate
            mi, m = i, x                  #track new maximum
        else:
            if i - mi >= k:                    #gap from last maximum big enough
                mit, mt = a[i - k]               #get incremental maximum at gap
                maxes = max(maxes,(mt, x, mit, i))  #check max pair candidate
        a[i] = (mi, m) # fill [a] with incremental maximums

    print(maxes) #find maximum pair candidate