Python based on sort, avoid hash


  • 0
    S

    Based on sorting of points and slope to the previous points. Avoid the potential issue with float hash key. But the code is lengthy and cmp doesn't work in python 3.0+

    class Solution(object):
        def maxPoints(self, points):
            """
            :type points: List[Point]
            :rtype: int
            """
            def compare(a,b):
                if a.x == b.x and a.y == b.y: return 0
                if a.x < b.x: return -1
                if a.x > b.x: return 1
                if a.y < b.y: return -1
                if a.y > b.y: return 1
            
            def slopeTo(a,b):
                dx,dy = a.x-b.x,a.y-b.y
                slope = dy*1.0/dx if dx!=0 else 1<<31
                return slope
    
            points.sort(cmp = compare)    
            l,i = 0,0
            
            res = 0
            
            while i < len(points):
                if i+1 < len(points) and compare(points[i],points[i+1]) == 0:
                    i += 1
                    continue
                replicates = i-l+1
                remain = points[i+1:]
                remain.sort(key = lambda x: slopeTo(points[i],x))
                ll,j=0,0
                while j < len(remain):
                    if j+1 < len(remain) and slopeTo(points[i],remain[j+1]) == slopeTo(points[i],remain[j]):
                        j += 1
                        continue
                    res = max(res,j-ll+1+replicates)
                    j += 1
                    ll = j
                res = max(res,replicates)
                i += 1
                l = i 
                
            return res

Log in to reply
 

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