找到元素之间距离不大于1的最长子数组 [英] Find the longest sub array where the distance between the elements is not bigger than one

问题描述

我有这个数组，例如:[1, 1, 2, 3, 4, 5])

所以我想要的数组是[1,1,2]，我写了这段代码:

def 比较(arr, n):我 = 0ct = 0打印(呼叫")而 i + len(arr)-n <= len(arr):打印(arr[i:len(arr)-n+i])如果 max(arr[i:len(arr)-n+i]) - min(arr[i:len(arr)-n+i]) == 1:打印(更改于:"+ str(n))ct = 1休息我 += 1如果 ct == 0:l = arrComparison(arr, n+1)返回 l别的:返回 n定义最长子数组(arr):menor = min(arr)市长 = max(arr)n = 0如果市长-menor >1:n = arrComparison(arr, 1)返回 len(arr) - n

函数LongestSubarray"在哪里只测试最长的子数组是否不是数组本身，如果不是，他们调用另一个，它沿着数组一步步移动，n"表示子数组中未被选中的数字的数量，即当 n=2 时，子数组将是:

[1,1,2,3], [1,2,3,4], [2,3,4,5]

当它找到第一个时，他们就中断并返回 n.这实际上解决了这个问题，但它在很长时间内解决了问题，所以我想要一种更优化的方式.

解决方案

这是一个使用 numpy 的矢量解决方案.基本上，它将数组与其自身进行比较(因此复杂性是二次的)以计算差异，然后从对角线上找到低于阈值的最长延伸:

将 numpy 导入为 np定义最长(arr，n = 1):# 确保 numpy 数组arr = np.array(arr)# 在上三角形上计算其自身的绝对差异矩阵# 根据 diff > 生成布尔值临界点差异 = (np.argmax(np.c_[np.triu(np.abs(arr-arr[:,None])>n),np.ones(len(arr)) # 处理数组均匀的情况],轴=1)-np.arange(len(arr)) # 减去对角线位置)# 获取第一个不匹配值的位置(值是拉伸长度)m = np.argmax(diffs)返回 arr[m:m+diffs[m]].tolist()

示例:

<预><代码>>>>最长([1,1,2,3,4,5])[1, 1, 2]>>>最长([1,1,2,3,4,5]，n=2)[1, 1, 2, 3]>>>最长([1,1,1,1,1,1,1])[1,1,1,1,1,1,1]>>>最长的([9, 8, 7, 6, 7])[7, 6, 7]>>>np.random.seed(0)>>>最长的(np.random.randint(0, 50, size=10000), n=2)[49, 47, 49, 49, 47]

I have this array, for example: [1, 1, 2, 3, 4, 5])

So the array that I want is [1,1,2], I wrote this code:

def Comparison(arr, n):

    i = 0
    ct = 0
    print("call")
    while i + len(arr)-n <= len(arr):
        print(arr[i:len(arr)-n+i])
        if max(arr[i:len(arr)-n+i]) - min(arr[i:len(arr)-n+i]) == 1:
            print("change at: "+str(n))
            ct = 1
            break
        i += 1
    if ct == 0:
        l = arrComparison(arr, n+1)
        return l
    else:
        return n

def longestSubarray(arr):

    menor = min(arr)
    mayor = max(arr)
    n = 0
    if mayor - menor > 1:
        n = arrComparison(arr, 1)

    return len(arr) - n

Where the function "LongestSubarray" just test if the longest subarray is not the array itself, and if it not, them call the other one, which is moving along the array step by step and the "n" represents the quantity of numbers that are not being selected in the subarray,, i.e. when n=2 the subarrays are going to be:

[1,1,2,3], [1,2,3,4], [2,3,4,5]

And them when it found the first one just break and return the n. This actually solve the question, but it does in a terrible long time, So I'd like for a more optimized way.

解决方案

Here is a vectorial solution with numpy. Basically, it compares the array with itself (the complexity is thus quadratic) to compute the differences and then finds the longest stretch below threshold from the diagonal:

import numpy as np
def longest(arr, n=1):
    # ensure numpy array
    arr = np.array(arr)
    # calculate absolute diff matrix with itself on upper triangle
    # make boolean based on diff > threshold
    diffs = (np.argmax(np.c_[np.triu(np.abs(arr-arr[:,None])>n),
                             np.ones(len(arr)) # this handles the case where array is uniform
                            ],
                      axis=1)
             -np.arange(len(arr)) # subtract position of diagonal
            )
    # get position of first non matching value (value is length of stretch)
    m = np.argmax(diffs)
    return arr[m:m+diffs[m]].tolist()

examples:

>>> longest([1,1,2,3,4,5]) 
[1, 1, 2]

>>> longest([1,1,2,3,4,5], n=2) 
[1, 1, 2, 3]

>>> longest([1,1,1,1,1,1,1])
[1,1,1,1,1,1,1]

>>> longest([9, 8, 7, 6, 7])
[7, 6, 7]

>>> np.random.seed(0)
>>> longest(np.random.randint(0, 50, size=10000), n=2)
[49, 47, 49, 49, 47]

这篇关于找到元素之间距离不大于1的最长子数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！