Python, Straightforward with Explanation


  • 14

    Let count[x] be the number of x's in our array.
    Suppose our longest subsequence B has min(B) = x and max(B) = x+1.
    Evidently, it should use all occurrences of x and x+1 to maximize it's length, so len(B) = count[x] + count[x+1].
    Additionally, it must use x and x+1 atleast once, so count[x] and count[x+1] should both be positive.

    def findLHS(self, A):
        count = collections.Counter(A)
        ans = 0
        for x in count:
            if x+1 in count:
                ans = max(ans, count[x] + count[x+1])
        return ans
    

    Alternatively, we can count values in a straightforward way using a dictionary: replacing our first line of count = collections.Counter(A) with:

    count = {}
    for x in A:
        count[x] = count.get(x, 0) + 1
    

  • 0
    J

    @awice your codes are very convenient and efficiency , and the answers are all right in my PC. But on the leetcode , the iteration of ''' for x in count ''' only iterate one time, could you tell me the reason? Thank you :)


  • 0

    @Jaylan count is a dictionary mapping values in our array to the number of times they occur. For example, if our array is A = [1, 1, 1, 2, 5, 5, 5], then our dictionary will be count = {1: 3, 2: 1, 5: 3}. When we iterate over count, we iterate over it's keys. So for x in count will loop through it's inner block three times, with the variable x = 1, x = 2, and x = 5.


  • 1

    The same:

    def findLHS(self, nums):
            c = collections.Counter(nums)
            return max(c[x] + c[x + 1] if c[x + 1] else 0 for x in c) if nums else 0

  • 0
    R

    Is the time complexity O(n)? and how to return the sub sequence array


  • 0
    L
    This post is deleted!

  • 0

    @retrocodr The code below gives you the subsequence and it's O(n). Since we know which number can be used as the LHS, we can record this number and find out the subsequence by looking the array again.

    class Solution(object):
        def findLHS(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            ans = 0
            ansNum = None
            d = collections.Counter(nums)
            for num in nums:
                if num + 1 in d:
                    if d[num] + d[num + 1] > ans:
                        ans = d[num] + d[num + 1]
                        ansNum = num
            res = []
            for num in nums:
                if num in [ansNum, ansNum + 1]:
                    res.append(num)
            return ans
    

  • 0
    L

    @awice said in Python, Straightforward with Explanation:

    ans
    This doesn't seem to preserve the original order, does it? I thought subsequence needs to maintain original element's order, only to remove certain elements.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.