O(n^2) TLE for python??


  • 0
    H
    class Solution:
        def get_line_equation(self, p1, p2):
            x1, y1 = p1
            x2, y2 = p2
            x1 = float(x1)
            y1 = float(y1)
            return (y2-y1, -(x2-x1), (x2-x1)*y1-(y2-y1)*x1)
    
        def get_line_hash(self, p1, p2):
            a, b, c = self.get_line_equation(p1, p2)
            if b == 0:
                if a == 0: return ""
                slope = "inf"
                inter = "%.6f" % round(c / a, 6)
            else:
                slope = "%.6f" % round(a / b, 6)
                inter = "%.6f" % round(c / b, 6)
    
            return "%s %s" % (slope, inter)
    
        # @param points, a list of Points
        # @return an integer
        def maxPoints(self, points):
            ans = 1 if points else 0
            count = collections.defaultdict(set)
            for i in range(len(points)):
                for j in range(i + 1, len(points)):
                    line_hash = self.get_line_hash((points[i].x, points[i].y), (points[j].x, points[j].y))
                    count[line_hash].add(points[i])
                    count[line_hash].add(points[j])
                    if ans < len(count[line_hash]): ans = len(count[line_hash])
    
            return ans

  • 0
    O
    def get_line_hash(self, p1, p2):
        a, b, c = self.get_line_equation(p1, p2)
        if b == 0:
            if a == 0: return ""
            slope = "inf"
            inter = "%.6f" % round(c / a, 6)
        else:
            slope = "%.6f" % round(a / b, 6)
            inter = "%.6f" % round(c / b, 6)
    
        return "%s %s" % (slope, inter)
    

    Parsing float to str would be very slow. I remove the (%s %s) % part in the return statement, TLE has gone but it appears to be WA.


Log in to reply
 

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