面试题性能优化：求从原点出发覆盖所有给定点的最少直线数

Hey Marcus, let's break down why your current slope-based approach is underperforming and how to optimize it for better speed and accuracy.

What's Holding Back Your Original Solution? #

Storing slopes in a set makes intuitive sense, but it has a few critical issues that hurt performance (and even correctness):

• Floating-point overhead: Calculating and hashing floating-point numbers is slower than working with integers—this adds up quickly for large datasets.
• Unnecessary duplicate work: If your input has duplicate points, you're re-computing the same slope over and over before the set deduplicates it.
• Hidden precision risks: Some slopes (like 1/3) can't be represented exactly as floats, which might lead to false duplicates or missed matches (a correctness issue that can also indirectly waste processing time).

Optimized Approach: Use Simplified Integer Ratios #

Instead of floats, represent each line by its simplified integer ratio of rise over run. This eliminates floating-point operations entirely and makes hashing faster and more reliable. Here's how to implement it:

Step-by-Step Breakdown

1. Deduplicate points first: Remove duplicate points upfront to cut down redundant calculations.
2. Handle edge cases:
   • Return 0 if the input is empty.
   • Return 0 if all points are the origin (no lines needed to intersect the starting point).
   • Use special markers for vertical (x=0) and horizontal (y=0) lines instead of ratios.
3. Simplify the slope ratio:
   • For a point (x, y), compute the greatest common divisor (GCD) of |x| and |y|.
   • Divide both x and y by the GCD to get the reduced form.
   • Normalize the sign: Ensure the denominator (x component) is positive so equivalent slopes (like 2/1 and -2/-1) get the same key.

Example Code (Python)

import math

def count_lines_from_origin(points):
    # Remove duplicate points to avoid redundant computations
    unique_points = set(points)
    
    # Handle empty input scenario
    if not unique_points:
        return 0
    
    # If all points are the origin, no lines are needed
    if unique_points == {(0, 0)}:
        return 0
    
    line_signatures = set()
    
    for x, y in unique_points:
        # Skip the origin itself (no line needed to intersect it)
        if x == 0 and y == 0:
            continue
        
        # Marker for vertical lines (infinite slope)
        if x == 0:
            line_signatures.add(("vertical",))
            continue
        
        # Marker for horizontal lines (slope 0)
        if y == 0:
            line_signatures.add(("horizontal",))
            continue
        
        # Calculate simplified rise/run ratio
        gcd_val = math.gcd(abs(x), abs(y))
        reduced_x = x // gcd_val
        reduced_y = y // gcd_val
        
        # Normalize to ensure consistent sign for equivalent slopes
        if reduced_x < 0:
            reduced_x = -reduced_x
            reduced_y = -reduced_y
        
        # Store the normalized slope as a tuple
        line_signatures.add((reduced_y, reduced_x))
    
    return len(line_signatures)

Why This Is Faster #

• Integer operations are more efficient: Calculating GCD and working with integers is far quicker than floating-point arithmetic, especially for large datasets.
• Less hash overhead: Hashing integer tuples is faster and more consistent than hashing floats.
• Reduced workload: Deduplicating points upfront cuts down the number of iterations your loop needs to handle.

Test Case Verification #

For your example input [(-1, -2), (1, 2), (2, 4), (2, 3)]:

• (-1,-2) simplifies to (2,1) (after sign normalization)
• (1,2) simplifies to (2,1)
• (2,4) simplifies to (2,1)
• (2,3) simplifies to (3,2)
• The set ends up with 2 elements, so the function returns 2—perfectly correct!

内容的提问来源于stack exchange，提问作者Marcus Lind