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 maximumdef 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))总结
以上是内存溢出为你收集整理的在数组中找到最长的升序(Python)全部内容,希望文章能够帮你解决在数组中找到最长的升序(Python)所遇到的程序开发问题。
如果觉得内存溢出网站内容还不错,欢迎将内存溢出网站推荐给程序员好友。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)