Algorithm Design and Analysis The second week of the operation of the leetcode

topic requires finding the maximum number of points on the same line. At first glance, it is relatively simple, so the slope is directly solved, and the slope is the same in a straight line. But soon began to expose the problem,

  • 一一 may have different point positions coincident
  • 二 is the accuracy of the slope should be stored in the way, because if you use floating point number storage, then there will be accuracy problems Especially when the horizontal and vertical coordinates of the point are relatively large, precision errors will occur, which will affect the operation result.
  • The third point to consider is the data storage structure. For example, I started storing it in struct+vector mode, but I need the complexity of o(n) when searching for points with the same slope, which is obviously not as direct map as map. efficient.
// The original data structure 
struct Slope {
    float slope;
    int times;
    Slope(float s,int t) :slope(s), times(t) {}
};

So for the above three points, the following is made as follows:

  • will coincide the points with map< pair< int, int>, int> pointsMap To re-weight
  • for slope accuracy problems, use string to store the dividend and divisor, and divide by the greatest common diminutum before storage.
  • For the data storage structure, use the structure of map < string, int > instead of struct slope+ vector < slope >
//The original code 
class Solution {
    struct Slope {
        float slope;
        int times;
        Slope(float s,int t) :slope(s), times(t) {}
    };
    float slopeTemp;
    vector<Slope> SlopeVec;
    int samepoint;
    bool isPush;
    public:
        int maxPoints(vector<Point>& points) {//the input of []Slope Ss(LONG_MAX, 0);// is used to store SlopeVec.push_back(ss) with equal abscissa; if (points.size() == 0) {
                return 0;
            }
            for (int i = 0; i < points.size(); i++) {
                samepoint = 0;
                for (int j = i+1; j < points.size(); j++) {
                    isPush = false;
                    if (points[i].x == points[j].x &&points[i].y == points[j].y) {
                        samepoint++;
                    }
                    else if (points[i].x == points[j].x) {
                        SlopeVec[0].times++;
                        break;
                    }
                    slopeTemp = (float)(points[i].y - points[j].y) / (float)(points[i].x - points[j].x);
                    for (int x = 1; x < SlopeVec.size(); x++) {//The zeroth position is used to store the abscissa equal to 
                        if ( fabs(slopeTemp-SlopeVec[x].slope)<1e-6 ) {
                            SlopeVec[x].times++;
                            isPush = true;
                        }
                    }
                    if (!isPush) {
                        Slope slope(slopeTemp, 1);
                        SlopeVec.push_back(slope);
                    }       
                }
            }
            int maxTimes = 0;
            for (int i = 0; i < SlopeVec.size(); i++) {
                if (SlopeVec[i].times > maxTimes) {
                    maxTimes = SlopeVec[i].times;
                }
            }
            int result = 1;
            while (maxTimes  != 1) {
                maxTimes = maxTimes - result;
                result++;
            }
            return result;
        }
};

Through the code, but the efficiency is not high enough, but the understanding is more convenient, first use map to de-weight, and then use the map of the record slope to store the number of points on the same slope.

class Solution {
    map<pair<int, int>, int> pointsMap;
    int samepoint;
    int sameX;
    int result, resultTemp;
    int xLength, yLength, g;
public:
    /* Iterative method (recursive method): Euclidean algorithm, calculate the greatest common divisor */
    int gcd(int m, int n) {
        while (m>0) {
            int c = n % m;
            n = m;
            m = c;
        }
        return n;
    }
    int maxPoints(vector<Point>& points) {// and [] input result =0;
        if (points.size() == 0) {
            return 0;
        }
        for (int i = 0; i < points.size(); i++) {
            pair<int, int> pairTemp(points[i].x, points[i].y);
            pointsMap[pairTemp]++;
        }
        for (auto i = pointsMap.begin(); i != pointsMap.end(); i++) {
            sameX = 0;
            resultTemp = 0;
            map<string, int> slopeMap;
            for (auto j = i; j != pointsMap.end(); j++) {
                if (i == j) {
                    continue;
                }
                if (i->first.first == j->first.first) {//points[i].x == points[j].x
                    pair<int, int> temp(j->first.first, j->first.second);
                    sameX += pointsMap[temp];
                }
                else {
                    xLength = i->first.first - j->first.first;
                    yLength = i->first.second - j->first.second;//points[i].y - points[j].y;    
                    g = gcd(abs(xLength), abs(yLength));// The first coefficient cannot be 0xLength /= g;
                    yLength /= g;if (yLength < 0) {//Ensure that the length of y is positiveyLength *= -1;
                        xLength *= -1;
                    }
                    stringstream ss;
                    ss << xLength << "," << yLength;
                    string slopeStr(ss.str());
                    pair<int, int> temp(j->first.first, j->first.second);
                    slopeMap[slopeStr] += pointsMap[temp];
                    resultTemp = max(resultTemp, slopeMap[slopeStr]);// find the slope of the most points under the same slope}
            }
            resultTemp = max(resultTemp, sameX);// Find the number of points in the same column as this pointpair<int, int> temp(i->first.first, i->first.second);
            result = max(result, resultTemp + pointsMap[temp]);
        }
        return result;
    }
};