在数组中找到最长的升序(Python)
发布时间:2020-12-20 13:20:10 所属栏目:Python 来源:网络整理
导读:比如,给你一组数字 nums = [2,5,3,4,6] 并且希望获得尽可能长的数字序列,这些数字在维持其顺序的同时是提升的,但不一定是结果. 所以最长的数字数组,其中An 1.在这种情况下: [2,6] 我通过递归和循环完成了这项工作,测试了所有可能性.然而,对于较大的阵列而言
比如,给你一组数字
nums = [2,5,3,4,6] 并且希望获得尽可能长的数字序列,这些数字在维持其顺序的同时是提升的,但不一定是结果. 所以最长的数字数组,其中An< 1.在这种情况下: [2,6] 我通过递归和循环完成了这项工作,测试了所有可能性.然而,对于较大的阵列而言,这需要花费太多时间 提前致谢! 这是我之前的代码,它返回了最终数组的长度 def bestLine(arr): maximum = 0 for i in range(0,len(arr)): if (len(arr)-i < maximum): break maximum = max(maximum,f(i,len(arr),arr)) return maximum def f(start,end,arr): best = 0 for i in range(start+1,end): if (end-i < best): break if (arr[i] > arr[start]): best = max(best,arr)) return 1 + best 解决方法
我的解决方案
def best_sequence_length(arr): '''Find length of the longest ascending sequence in an array''' arr_length = len(arr) if arr_length <= 1: return arr_length longest = [1] # will store the lengths of the longest sequence ending on this index best_idx_at_all = 0 for idx in range(1,arr_length): best_len_so_far = 1 back = -1 for i in range(len(longest)+1): if arr[i] < arr[idx] and best_len_so_far <= longest[i]: best_len_so_far = longest[i] + 1 back = i longest.append(longest[back]+1 if back > -1 else 1) if longest[best_idx_at_all] < longest[idx]: best_idx_at_all = idx return longest[best_idx_at_all] 这可能不是非常“pythonic”(它类似于C或甚至FORTRAN代码:-),但它具有O(n ^ 2)复杂度. 如果你想获得最长的序列,而不仅仅是它的长度(可能是模糊的),上面的函数只需要稍加修改: def best_sequence(arr): '''Find longest ascending sequence in an array''' arr_length = len(arr) if arr_length <= 1: return arr longest = [1] # will store the length of the longest sequence ending on this index back_link = [-1] # link to the previous element in the longest sequence or -1 best_idx_at_all = 0 for idx in range(1,arr_length): best_len_so_far = 1 back = -1 for i in range(len(longest)+1): if arr[i] < arr[idx] and best_len_so_far <= longest[i]: best_len_so_far = longest[i] + 1 back = i back_link.append(back) longest.append(longest[back]+1 if back > -1 else 1) if longest[best_idx_at_all] < longest[idx]: best_idx_at_all = idx nxt = best_idx_at_all result = [] while nxt >= 0: result.append(arr[nxt]) nxt = back_link[nxt] return list(reversed(result)) (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |