时间戳

首页 > 解决方案 > 查找两个最大且不连续值的索引

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

问题描述

给定以下向量，

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

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

idx = [2, 10]

（a[2] = 22；a[10] = 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)

标签： pythonsortingmax

解决方案

线性复杂度版本。
大约 O(N) 时间和恒定空间

它的工作原理是建立一个最大值到每个索引的列表，
然后检查每个元素和最大值到（当前元素的索引 - k），
这是因为最大值到（这个索引 - 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

推荐阅读