Finding neighbours in a list -Python-CodePudding

How to find the difference between neighboring numbers in a list whose difference is 1 and print the length of the longest series of neighbours within the list.

For example, in the list

[1, 2, 5, 4, 3, 4] the longest list of neighbours would be

[5, 4, 3, 4], with a length of 4.

I am stuck at this point,

    a = [1, 2, 5, 7, 6, 5, 6, 3, 4, 1, 0]
    b = []
    for i in range(len(a)-1):
        c = (abs(a[i] - a[i 1]))
        if c == 1:
            print(a[i])

CodePudding user response：

a = [1, 2, 5, 7, 6, 5, 6, 3, 4, 1, 0]
list_of_lengths = [] #to store the length of all series
k = 0 
old_series = False #to see if it's a new series or no
for i in range(len(a)-1):
    c = (abs(a[i] - a[i 1]))
    if c == 1 and old_series ==  False:
        k =1
        old_series = True
    if c == 1 and old_series :
        k =1
    if c != 1 and old_series :
        list_of_lengths.append(k)
        k=0
        old_series = False

if k>0 and old_series: #in case the last element is also in the series
    list_of_lengths.append(k)   
print(max(list_of_lengths))

>>> 4

CodePudding user response：

Usually when you want to find an extremum you hold two variables: current and best. In this case the best one is the longest sequence. So the most basic approach is to keep appending items to a list for as long as the property holds.

Let's try a naive solution: for each position in the list, calculate the longest sequence meeting the constraints:

def get_sequence(a, i):
    result = [a[i]]
    while i < len(a)-1 and abs(a[i] - a[i 1]) == 1:
        result.append(a[i 1])
        i  = 1
    return result

a = [1, 2, 5, 4, 3, 4]
longest = []
for i in range(len(a)):
    current = get_sequence(a, i)
    if len(current)> len(longest):
        longest = list(current)

print(longest)

The problem with this solution is that its complexity is O(n^2). And we can see that we are unnecessarily evaluating some subsequences more than once. If we've already checked that [2,3,4] is the longest subsequence starting with "2", there is no point trying to start from "3", because we already know the element after "4" doesn't meet the constraints. So we can take advantage of this property to have a solution that has linear complexity:

def get_sequence(a, i):
    result = [a[i]]
    while i < len(a)-1 and abs(a[i] - a[i 1]) == 1:
        result.append(a[i 1])
        i  = 1
    return result

a = [1, 2, 5, 4, 3, 4]
longest = []
i = 0
while i < len(a):
    current = get_sequence(a, i)
    if len(current)> len(longest):
        longest = list(current)
    i  = len(current)

print(longest)

Another possible solution, closer to what you've got right now and also O(n):

longest = []
current = [a[0]]
for i in range(len(a)):
  c = (abs(a[i] - a[i 1])) if i < len(a)-1 else 0
  if c == 1:
    current.append(a[i 1])
  else:
    if len(current) > len(longest):
      longest = list(current)
    current = [a[i 1]] if i < len(a)-1 else []

print(longest)

Seems a bit kludgey because of the end-list edge conditions - probably could use some improvement.