V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
lsmgeb89
V2EX  ›  算法

奇怪的 Leetcode Memory Limit Exceeded 错误

  •  
  •   lsmgeb89 · 2017-03-07 07:22:19 +08:00 · 8355 次点击
    这是一个创建于 2579 天前的主题,其中的信息可能已经有所发展或是发生改变。

    常规的 DP 题,最长单调递增子序列:

    https://leetcode.com/problems/longest-increasing-subsequence/

    我的代码:

    https://github.com/lsmgeb89/leetcode_solution/blob/master/medium/300-longest-increasing-subsequence-2.h

    提交后,最后一个很长的 case 会报 Memory Limit Exceeded 错误。

    但是很奇怪,我加了 remove duplicate 的代码还是会有这个错误。

    另外,这个代码并不只是输出长度,所以并不是最简,不要纠结于此,但是 O(nlog(n)) 的时间复杂度。

    那个 remove duplicate 的代码比较傻,但也不至于 Memory Limit Exceeded。

    我试过另一种方法 remove duplicate,也是一样。

    7 条回复    2017-03-09 10:25:40 +08:00
    jedihy
        1
    jedihy  
       2017-03-08 14:56:30 +08:00
    因为你的空间复杂度是 O(N^2),而实际上可以做到 O(n),因为你需要得到长度而不是子序列,所以只记录最后一个元素。另外推荐这样的地方用 upper_bound 而不是直接写个二分容易错,代码看起来也不太舒服。

    下面是我自己写的 python 的,给你参考下

    class Solution(object):
    def lengthOfLIS(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    tail = []
    for i in xrange(0, len(nums)):
    idx = bisect.bisect_right(tail, nums[i])
    if idx - 1 >= 0 and nums[i] == tail[idx - 1]:
    continue
    if idx == len(tail):
    tail.append(nums[i])
    else:
    tail[idx] = nums[i]
    return len(tail)
    jedihy
        3
    jedihy  
       2017-03-08 15:21:47 +08:00
    其次, nlogn 已经够快了,去重那一步没什么必要吧
    lsmgeb89
        4
    lsmgeb89  
    OP
       2017-03-08 19:51:11 +08:00 via Android
    @jedihy 谢谢回复。

    昨天由于没人回,自己也找了 O(n) 的版本。

    只吐槽一点,我估计 LeetCode 算的是所有 cases 加起来用的空间来判断的我触发 memory limit 了。

    但那个界面给人的感觉是只有那一个 case 超了 memory limit 。

    然后我就很 confused ,因为加了去重,即使是 O(n^2),就那一个 case 来说,实际用的空间也很小。

    去重是为了是减少一点空间,如果用了 O(n) 的版本,确实多余。
    lsmgeb89
        5
    lsmgeb89  
    OP
       2017-03-08 19:59:11 +08:00 via Android
    由于在做 CLRS 15.4-6 ,所以要输出序列的版本,而不只是长度。在这个条件下, O(n) 不是太容易想到。 LeetCode 只是借着用来测试下代码的正确性。
    jedihy
        6
    jedihy  
       2017-03-09 10:22:51 +08:00 via iPhone
    对,都是累积的,单个去算这个系统就太难设计了
    jedihy
        7
    jedihy  
       2017-03-09 10:25:40 +08:00 via iPhone
    我觉得这个 nlogn 的方法是自己想不出来的,我是在很久之前 geeksforgeeks 上看的
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2793 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 11:48 · PVG 19:48 · LAX 04:48 · JFK 07:48
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.