Räkna maximala poäng på samma rad
Prova det på GfG Practice 
Produktion
Givet n punkt på ett 2D-plan som par av (x y) koordinater behöver vi hitta maximalt antal punkter som ligger på samma linje.
Exempel:
Input : poäng[] = {-1 1} {0 0} {1 1}
{2 2} {3 3} {3 4}
Produktion : 4
Sedan maximalt antal punkter som ligger på samma
linjen är 4 dessa punkter är {0 0} {1 1} {2 2}
{3 3}
För varje punkt p beräkna dess lutning med andra punkter och använd en karta för att registrera hur många punkter som har samma lutning genom vilken vi kan ta reda på hur många punkter som ligger på samma linje med p som deras ena punkt. Fortsätt göra samma sak för varje poäng och uppdatera det maximala antalet poäng som hittats hittills.
Några saker att notera vid implementering är:
- om två punkter är (x1 y1) och (x2 y2) så blir deras lutning (y2 – y1) / (x2 – x1) vilket kan vara ett dubbelt värde och kan orsaka precisionsproblem. För att bli av med precisionsproblemen behandlar vi lutning som par ((y2 - y1) (x2 - x1)) istället för förhållande och reducerar par med deras gcd innan vi infogar i kartan. Nedan behandlas kodpunkter som är vertikala eller upprepade separat.
- Om vi använder Hash Map eller Dictionary för att lagra lutningsparet kommer den totala tidskomplexiteten för lösningen att vara O(n^2) och rymdkomplexiteten kommer att vara O(n).
/* C/C++ program to find maximum number of point which lie on same line */ #include #include using namespace std ; // method to find maximum collinear point int maxPointOnSameLine ( vector < pair < int int > > points ) { int N = points . size (); if ( N < 2 ) return N ; int maxPoint = 0 ; int curMax overlapPoints verticalPoints ; // here since we are using unordered_map // which is based on hash function //But by default we don't have hash function for pairs //so we'll use hash function defined in Boost library unordered_map < pair < int int > int boost :: hash < pair < int int > > > slopeMap ; // looping for each point for ( int i = 0 ; i < N ; i ++ ) { curMax = overlapPoints = verticalPoints = 0 ; // looping from i + 1 to ignore same pair again for ( int j = i + 1 ; j < N ; j ++ ) { // If both point are equal then just // increase overlapPoint count if ( points [ i ] == points [ j ]) overlapPoints ++ ; // If x co-ordinate is same then both // point are vertical to each other else if ( points [ i ]. first == points [ j ]. first ) verticalPoints ++ ; else { int yDif = points [ j ]. second - points [ i ]. second ; int xDif = points [ j ]. first - points [ i ]. first ; int g = __gcd ( xDif yDif ); // reducing the difference by their gcd yDif /= g ; xDif /= g ; // increasing the frequency of current slope // in map slopeMap [ make_pair ( yDif xDif )] ++ ; curMax = max ( curMax slopeMap [ make_pair ( yDif xDif )]); } curMax = max ( curMax verticalPoints ); } // updating global maximum by current point's maximum maxPoint = max ( maxPoint curMax + overlapPoints + 1 ); // printf('maximum collinear point // which contains current point // are : %dn' curMax + overlapPoints + 1); slopeMap . clear (); } return maxPoint ; } // Driver code int main () { const int N = 6 ; int arr [ N ][ 2 ] = {{ -1 1 } { 0 0 } { 1 1 } { 2 2 } { 3 3 } { 3 4 }}; vector < pair < int int > > points ; for ( int i = 0 ; i < N ; i ++ ) points . push_back ( make_pair ( arr [ i ][ 0 ] arr [ i ][ 1 ])); cout < < maxPointOnSameLine ( points ) < < endl ; return 0 ; }
Java /* Java program to find maximum number of point which lie on same line */ import java.util.* ; class GFG { static int gcd ( int p int q ) { if ( q == 0 ) { return p ; } int r = p % q ; return gcd ( q r ); } static int N = 6 ; // method to find maximum collinear point static int maxPointOnSameLine ( int [][] points ) { if ( N < 2 ) return N ; int maxPoint = 0 ; int curMax overlapPoints verticalPoints ; HashMap < String Integer > slopeMap = new HashMap <> (); // looping for each point for ( int i = 0 ; i < N ; i ++ ) { curMax = overlapPoints = verticalPoints = 0 ; // looping from i + 1 to ignore same pair again for ( int j = i + 1 ; j < N ; j ++ ) { // If both point are equal then just // increase overlapPoint count if ( points [ i ][ 0 ] == points [ j ][ 0 ] && points [ i ][ 1 ] == points [ j ][ 1 ] ) overlapPoints ++ ; // If x co-ordinate is same then both // point are vertical to each other else if ( points [ i ][ 0 ] == points [ j ][ 0 ] ) verticalPoints ++ ; else { int yDif = points [ j ][ 1 ] - points [ i ][ 1 ] ; int xDif = points [ j ][ 0 ] - points [ i ][ 0 ] ; int g = gcd ( xDif yDif ); // reducing the difference by their gcd yDif /= g ; xDif /= g ; // Convert the pair into a string to use // as dictionary key String pair = ( yDif ) + ' ' + ( xDif ); if ( ! slopeMap . containsKey ( pair )) slopeMap . put ( pair 0 ); // increasing the frequency of current // slope in map slopeMap . put ( pair slopeMap . get ( pair ) + 1 ); curMax = Math . max ( curMax slopeMap . get ( pair )); } curMax = Math . max ( curMax verticalPoints ); } // updating global maximum by current point's // maximum maxPoint = Math . max ( maxPoint curMax + overlapPoints + 1 ); slopeMap . clear (); } return maxPoint ; } public static void main ( String [] args ) { int points [][] = { { - 1 1 } { 0 0 } { 1 1 } { 2 2 } { 3 3 } { 3 4 } }; System . out . println ( maxPointOnSameLine ( points )); } }
Python # python3 program to find maximum number of 2D points that lie on the same line. from collections import defaultdict from math import gcd from typing import DefaultDict List Tuple IntPair = Tuple [ int int ] def normalized_slope ( a : IntPair b : IntPair ) -> IntPair : ''' Returns normalized (rise run) tuple. We won't return the actual rise/run result in order to avoid floating point math which leads to faulty comparisons. See https://en.wikipedia.org/wiki/Floating-point_arithmetic#Accuracy_problems ''' run = b [ 0 ] - a [ 0 ] # normalize undefined slopes to (1 0) if run == 0 : return ( 1 0 ) # normalize to left-to-right if run < 0 : a b = b a run = b [ 0 ] - a [ 0 ] rise = b [ 1 ] - a [ 1 ] # Normalize by greatest common divisor. # math.gcd only works on positive numbers. gcd_ = gcd ( abs ( rise ) run ) return ( rise // gcd_ run // gcd_ ) def maximum_points_on_same_line ( points : List [ List [ int ]]) -> int : # You need at least 3 points to potentially have non-collinear points. # For [0 2] points all points are on the same line. if len ( points ) < 3 : return len ( points ) # Note that every line we find will have at least 2 points. # There will be at least one line because len(points) >= 3. # Therefore it's safe to initialize to 0. max_val = 0 for a_index in range ( 0 len ( points ) - 1 ): # All lines in this iteration go through point a. # Note that lines a-b and a-c cannot be parallel. # Therefore if lines a-b and a-c have the same slope they're the same # line. a = tuple ( points [ a_index ]) # Fresh lines already have a so default=1 slope_counts : DefaultDict [ IntPair int ] = defaultdict ( lambda : 1 ) for b_index in range ( a_index + 1 len ( points )): b = tuple ( points [ b_index ]) slope_counts [ normalized_slope ( a b )] += 1 max_val = max ( max_val max ( slope_counts . values ()) ) return max_val print ( maximum_points_on_same_line ([ [ - 1 1 ] [ 0 0 ] [ 1 1 ] [ 2 2 ] [ 3 3 ] [ 3 4 ] ])) # This code is contributed by Jose Alvarado Torre
C# /* C# program to find maximum number of point which lie on same line */ using System ; using System.Collections.Generic ; class GFG { static int gcd ( int p int q ) { if ( q == 0 ) { return p ; } int r = p % q ; return gcd ( q r ); } static int N = 6 ; // method to find maximum collinear point static int maxPointOnSameLine ( int [ ] points ) { if ( N < 2 ) return N ; int maxPoint = 0 ; int curMax overlapPoints verticalPoints ; Dictionary < string int > slopeMap = new Dictionary < string int > (); // looping for each point for ( int i = 0 ; i < N ; i ++ ) { curMax = overlapPoints = verticalPoints = 0 ; // looping from i + 1 to ignore same pair again for ( int j = i + 1 ; j < N ; j ++ ) { // If both point are equal then just // increase overlapPoint count if ( points [ i 0 ] == points [ j 0 ] && points [ i 1 ] == points [ j 1 ]) overlapPoints ++ ; // If x co-ordinate is same then both // point are vertical to each other else if ( points [ i 0 ] == points [ j 0 ]) verticalPoints ++ ; else { int yDif = points [ j 1 ] - points [ i 1 ]; int xDif = points [ j 0 ] - points [ i 0 ]; int g = gcd ( xDif yDif ); // reducing the difference by their gcd yDif /= g ; xDif /= g ; // Convert the pair into a string to use // as dictionary key string pair = Convert . ToString ( yDif ) + ' ' + Convert . ToString ( xDif ); if ( ! slopeMap . ContainsKey ( pair )) slopeMap [ pair ] = 0 ; // increasing the frequency of current // slope in map slopeMap [ pair ] ++ ; curMax = Math . Max ( curMax slopeMap [ pair ]); } curMax = Math . Max ( curMax verticalPoints ); } // updating global maximum by current point's // maximum maxPoint = Math . Max ( maxPoint curMax + overlapPoints + 1 ); slopeMap . Clear (); } return maxPoint ; } // Driver code public static void Main ( string [] args ) { int [ ] points = { { - 1 1 } { 0 0 } { 1 1 } { 2 2 } { 3 3 } { 3 4 } }; Console . WriteLine ( maxPointOnSameLine ( points )); } } // This code is contributed by phasing17
JavaScript /* JavaScript program to find maximum number of point which lie on same line */ // Function to find gcd of two numbers let gcd = function ( a b ) { if ( ! b ) { return a ; } return gcd ( b a % b ); } // method to find maximum collinear point function maxPointOnSameLine ( points ){ let N = points . length ; if ( N < 2 ){ return N ; } let maxPoint = 0 ; let curMax overlapPoints verticalPoints ; // Creating a map for storing the data. let slopeMap = new Map (); // looping for each point for ( let i = 0 ; i < N ; i ++ ) { curMax = 0 ; overlapPoints = 0 ; verticalPoints = 0 ; // looping from i + 1 to ignore same pair again for ( let j = i + 1 ; j < N ; j ++ ) { // If both point are equal then just // increase overlapPoint count if ( points [ i ] === points [ j ]){ overlapPoints ++ ; } // If x co-ordinate is same then both // point are vertical to each other else if ( points [ i ][ 0 ] === points [ j ][ 0 ]){ verticalPoints ++ ; } else { let yDif = points [ j ][ 1 ] - points [ i ][ 1 ]; let xDif = points [ j ][ 0 ] - points [ i ][ 0 ]; let g = gcd ( xDif yDif ); // reducing the difference by their gcd yDif = Math . floor ( yDif / g ); xDif = Math . floor ( xDif / g ); // increasing the frequency of current slope. let tmp = [ yDif xDif ]; if ( slopeMap . has ( tmp . join ( '' ))){ slopeMap . set ( tmp . join ( '' ) slopeMap . get ( tmp . join ( '' )) + 1 ); } else { slopeMap . set ( tmp . join ( '' ) 1 ); } curMax = Math . max ( curMax slopeMap . get ( tmp . join ( '' ))); } curMax = Math . max ( curMax verticalPoints ); } // updating global maximum by current point's maximum maxPoint = Math . max ( maxPoint curMax + overlapPoints + 1 ); // printf('maximum collinear point // which contains current point // are : %dn' curMax + overlapPoints + 1); slopeMap . clear (); } return maxPoint ; } // Driver code { let N = 6 ; let arr = [[ - 1 1 ] [ 0 0 ] [ 1 1 ] [ 2 2 ] [ 3 3 ] [ 3 4 ]]; console . log ( maxPointOnSameLine ( arr )); } // The code is contributed by Gautam goel (gautamgoel962)
Produktion
4
Tidskomplexitet: På 2 lugna) där n anger strängens längd.
Hjälputrymme: O(n)
