Python：如何有效地檢查序列是否正在增加

Question

該代碼的目標是查看序列是否幾乎增加，也就是說，可以通過刪除單個元素來嚴格增加序列。

例如：[1, 3, 2, 3]將嚴格增加，如果在索引1的元素被刪除。 [1, 2, 1, 2]幾乎沒有增加，因爲如果你刪除了第一個'2'，你會得到[1, 1, 2]這不是嚴格增加。

我的代碼必須在4000毫秒內工作，其長度爲2 <= len <= 10^5。它很可能被很長的序列所困擾。

下面是代碼：

def almostIncreasingSequence(sequence): 
    for i in range(len(sequence)): 
     c = sequence.pop(i) 
     if sequence == sorted(sequence): 
      for item in sequence: 
       if sequence.count(item) != 1: 
        break 
      else: 
       return True 
     sequence.insert(i, c) 
    return False 

Answer 1

您的「幾乎增加」條件可與以下兩條規則被改寫：

1. 至多有一個位置i列表不滿足ai < ai+1 。
2. 位置周圍的元素滿足條件ai < ai+2。

這是一個可以很容易地在O(n)時間來評估一個問題：

def almostIncreasingSequence(sequence): 
    iterator = iter(enumerate(sequence)) 
    prev = next(iterator) 
    found = False 
    for item in iterator: 
     if item[1] <= prev[1]: 
      if found: 
       return False 
      if prev[0] > 0 and item[0] < len(sequence) - 1 \ 
          and sequence[prev[0] - 1] >= item[1]: 
       return False 
      found = True 
     prev = item 
    return True 

如果你被允許使用numpy的：

def almostIncreasingSequence(sequence): 
    ind = np.where(np.diff(sequence) <= 0)[0] 
    if len(ind) > 1: 
     return False 
    if len(ind) == 1 and (ind[0] == 0 or ind[0] == len(sequence) - 2): 
     return True 
    if len(ind) == 0: 
     return True 
    return sequence[ind[0] + 1] > sequence[ind[0] - 1] 

選擇樹是清晰。它可以被改寫爲一個return語句：

return len(ind) == 0 or \ 
      (len(ind) == 1 and (ind[0] == 0 or \ 
           ind[0] == len(sequence) - 1 or \ 
           sequence[ind[0] - 1] < sequence[ind[0] + 1])) 

這些解決方案都能夠正確應對邊緣情況下，像[6, 5, 6, 7]和[1, 2, 3, 1]。

Answer 2

計算相鄰元素的差異sequence並找出它多久沒有增加（即區別在於如何往往不是正面）：

def almost_increasing(seq): 
    if type(seq)==type([]): 
     seq = np.array(seq) 
    diff = seq[1:] - seq[:-1] # differences of neighboring elements 
    indices = np.where(diff <= 0)[0] 
    if len(indices) == 0: return True # increasing sequence, case 1 
    elif len(indices) == 1 and indices[0] == len(seq) - 2: return True # non-increase only at last element, case 2 
    elif len(indices) == 1 and indices[0] == len(seq) - 1 and seq[-3] < seq[-1]: return True # non-increase only at forelast element, case 3 
    elif len(indices) == 1 and seq[indices[0]-1] < seq[indices[0]+1]: return True # case 4 
    elif len(indices) == 1 and seq[indices[0]] < seq[indices[0]+2]: return True # case 5 
    else: return False 

# For understanding, maybe insert print(indices) 
print(almost_increasing([1,2,3])) # case 1 
print(almost_increasing([1,2,3,4,1])) # case 2 
print(almost_increasing([1,2,3,1,4])) # case 3 
print(almost_increasing([1,3,2,3])) # case 4 
print(almost_increasing([1,2,1,4])) # case 5 
print(almost_increasing([1,2,1,2])) 

# performance 
import time 
start = time.clock() 
almost_increasing(np.random.random(100000)) 
stop = time.clock() 
print(stop-start) 

情況4和5在選擇從序列中刪除的元素方面有所不同。

Answer 3

如果你提供了一些測試，這將是很好的：p但我嘗試了一些好處，當尺寸高於3時要考慮連續性是很重要的。只需要區分這個列表並確保n-3是一個。希望我沒有弄錯

import itertools 
import numpy as np 

def ais(sequence): 
    if len(sequence) < 3: # trivial cases for length 1 and 2 
     return True 
    if len(sequence)==3: # can afford a lazy look 
     for perm in itertools.permutations(sequence): 
      if perm[1:][1]-perm[1:][0] == 1: 
       return True 
     return False 
    else: 
     return list(np.diff(sequence)).count(1) == (len(sequence)-3)