python - 返回最长摆动子数组
问题描述
给定一个数字数组(或在本例中为 pandas 系列)返回最长的摆动子数组。摆动数组是这样一种数组,即数字在方向上交替 - 它们严格地上下波动。IE
Input: [10, 22, 9, 33, 49, 50, 31, 60, 15]
Output: [49, 50, 31, 60, 15]
数组必须按顺序形成,即不能通过跳过值来形成数组。
我的天真蛮力方法可以在下面找到 - 我很难让它发挥作用。有小费吗?
def zigzag(arr):
result = pd.Series([])
for i in range(len(arr)-2):
if arr[i:i+3] != sorted(arr[i:i+3]) and arr[i:i+3] != sorted(arr[i:i+3], reverse = True): # no three points increase or decrease
result = result.append(pd.Series(arr[i:i+3], index = list(range(i, i+3))))
result = result.loc[~result.index.duplicated(keep='first')]
else:
result = pd.Series([])
return result
解决方案
您可以通过迭代和检查zigzag条件来实现具有线性复杂性的贪婪解决方案,贪婪地获取元素,直到达到破坏条件的元素然后最大化答案(您已经拥有的不破坏条件的范围)并从当前元素(打破条件的元素)开始重复操作。
这是有效的,因为如果一个元素打破了条件,那么就没有更好的答案,包括该元素之前的范围和之后的范围。
我不在我的机器上运行代码,但这里有一个例子(按照评论):
def zigzag(arr):
mx, cur, lst, op = 0, 0, -1, 0
st, en = 0, 0
ans = 0
for i, x in enumerate(arr):
# if its the first element we take it greedily
if lst == -1:
lst = x
st = i
# else if lst is the first element taken then decide which direction we need next
elif op == 0:
if x > lst:
op = 1
elif x < lst:
op = -1
# if current element is equal to last taken element we stop and start counting from this element
else:
# check if current range is better than previously taken one
if i-st > mx:
mx = i-st
ans = st
en = i
st = i
op = 0
lst = x
else:
# if direction meets the inequality take the current element
if (op == 1 and x < lst) or (op == -1 and x > lst):
op *= -1
lst = x
# otherwise, check if the current range is better than the previously taken one
else:
if i-st > mx:
mx = i-st
ans = st
en = i
st = i
lst = x
op = 0
# if starting index is greater than or equal to the last, then we have reached the end without checking for maximum range
if st >= en:
if len(arr)-st > en-ans:
ans = st
en = len(arr)
result = [arr[i] for i in range(ans, en)]
return result
print(zigzag([10, 22, 9, 33, 49, 50, 31, 60, 15]))
# [49, 50, 31, 60, 15]
推荐阅读
- python - 在处理带有 None 的行时,在 pandas 列中提取 JSON 以分隔列
- vba - 如何使用 VBA 将图像裁剪为特定形式,例如 PowerPoint 中的圆圈?
- office365api - asp dotnet core如何连接邮箱
- powershell - 如何模拟点源脚本?
- php - PHP - 多维数组检查重复项(没有 array_unique)
- c# - 使用linq或数据视图过滤器从c#中的DataTable中获取最高日期行
- scala - 类型别名和隐式值解析
- apache-spark - 线程“main”java.sql.SQLException 中的异常:运行 spark-submit 时没有合适的驱动程序
- django - 在 django 中访问 api 时您无权执行此操作
- python - 在 Keras 的 lstm 网络中使用哪个激活函数进行序列预测?