我有一个索引列表:
[24, 175, 78, 80, 659, 126, 141, 149, 29, 158, 178, 179]
我想知道如何识别(并删除)哪些是无序的
期望结果:
[24, 78, 80, 126, 141, 149, 158, 178, 179]
作为一个人，我看到175、659和29很突出，但不确定如何通过编程来实现。我已经尝试了两两比较(如果sub_arr[0]<sub_arr[1]_x002E_=">
new_ls = []
def eval_adjacent(ls):
if ls[1] > ls[0]:
return ls[0]
for n, ele in enumerate(idx_ls[:-1]):
res = eval_adjacent(idx_ls[n:n+2])
if res:
new_ls.append(res)
然而，如果整数小于它应该是，这将不起作用(29)。我想过在两个方向上迭代，但我开始认为这不是可行的方法。
我认为将其与排序(ls)进行比较可能更容易-但我不确定如何选择需要的(拒绝其余部分)。
谁能给我指个正确的方向?似乎你想要最长的递增子序列。
试试这个:
from math import floor
# from https://en.wikipedia.org/wiki/Longest_increasing_subsequence
def lis(X):
N = len(X)
P = [0] * N
M = [0] * N
M[0] = -1
L = 0
for i in range(N):
lo = 1
hi = L + 1
while lo < hi:
mid = lo + floor((hi-lo)/2)
if X[M[mid]] > X[i]:
hi = mid
else:
lo = mid + 1
newL = lo
P[i] = M[newL-1]
M[newL] = i
if newL > L:
L = newL
S = [0] * N
k = M[L]
for j in range(L-1, -1, -1):
S[j] = X[k]
k = P[k]
S = [el for el in S if el != 0]
return S
data = [24, 175, 78, 80, 659, 126, 141, 149, 29, 158, 178, 179]
print(lis(data)) # => [24, 78, 80, 126, 141, 149, 158, 178, 179]
您可以使用dynamic programming:
def long_inc_seq(lst):
dp = [[n] for n in lst]
for i in range(len(lst)):
for j in range(i):
if lst[i] > lst[j] and len(dp[i]) < len(dp[j]) + 1:
dp[i] = dp[j] + [lst[i]]
return max(dp, key=len)
result = long_inc_seq([24, 175, 78, 80, 659, 126, 141, 149, 29, 158, 178, 179])
print(result)
输出:
[24, 78, 80, 126, 141, 149, 158, 178, 179]
解释:
# The inside of dp for the above example:
>>> dp
[[24],
[24, 175],
[24, 78],
[24, 78, 80],
[24, 78, 80, 659],
[24, 78, 80, 126],
[24, 78, 80, 126, 141],
[24, 78, 80, 126, 141, 149],
[24, 29],
[24, 78, 80, 126, 141, 149, 158],
[24, 78, 80, 126, 141, 149, 158, 178],
[24, 78, 80, 126, 141, 149, 158, 178, 179]]
可以使用列表推导和窗口从more_itertools:
- 窗口的函数允许您创建集 的滑动窗口。
- 检查每个滑动窗口的数字是否无序 这些数字列在变量
nums_to_reject中，然后从indices的原始列表中删除，生成result代码:
from more_itertools import windowed
indices = [24, 175, 78, 80, 659, 126, 141, 149, 29, 158, 178, 179]
nums_to_reject = [item[1] for item in windowed(indices, 3) if item[0] < item[2] < item[1] or item[1] < item[2] > item[0] > item[1]]
result = sorted(list(set(indices) - set(nums_to_reject)))
print(result)
[24, 78, 80, 126, 141, 149, 158, 178, 179]
这是一个我认为任何类型的python程序员都可以理解的方法:(我假设没有2个后续数字无序)
my_list = [24, 175, 78, 80, 659, 126, 141, 149, 29, 158, 178, 179]
my_list2 = []
for i in range(len(my_list)):
try:
if not (my_list[i + 1] > my_list[i] and my_list[i + 1] > my_list[i + 2]):
my_list2.append(my_list[i + 1])
except(IndexError): # we add this to prevent INDEX OUT OF RANGE exception
pass
print(my_list2)
[78, 80, 126, 141, 29, 158, 178]