Is there a possible N^2 algorithm if points are in float?


  • 0
    K

    As most of the N^2 method is using harsh map with calculating the GCD, I wonder if it is possible to have an algorithm that doesn't utilize the integer characteristics.


  • 0
    K

    Expected O(N^2) algorithm using map, assuming that hash query can be finished in O(1) for pairs of floats.

    class Solution:
        # @param points, a list of Points
        # @return an integer
        def maxPoints(self, points):
            if len(points) == 0: return 0
            points = [(p.x, p.y) for p in points]
            d = collections.defaultdict(lambda: 0)
            for p in points: d[p] += 1
            length = len(points)
            unique_points = list(set(points))
            number_points = len(unique_points)
            if number_points == 1: return len(points)
            lines = collections.defaultdict(set)
            for i in xrange(number_points):
                for j in xrange(i+1, number_points):
                    if unique_points[i][0] == unique_points[j][0]:
                        k = float('inf')
                        b = unique_points[i][0]
                    else:
                        k = float(unique_points[i][1] - unique_points[j][1]) / (unique_points[i][0] - unique_points[j][0])
                        b = float(unique_points[i][0] * unique_points[j][1] - unique_points[j][0] * unique_points[i][1]) / (unique_points[i][0] - unique_points[j][0])
                    lines[(k, b)].add(unique_points[i])
                    lines[(k, b)].add(unique_points[j])
            maxcount = 0
            # Hashing
            for l, s in lines.items():
                count = 0
                for p in s:
                    count += d[p]
                maxcount = max(maxcount, count)
            return maxcount
    

Log in to reply
 

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