題目描述

?

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

?

我的想法：

1、算法設(shè)計(jì)很簡單的題目，但是真正用數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)起來卻不容易的一道題。

2、剛開始考慮分三類進(jìn)行解決，一類橫坐標(biāo)相同，一類縱坐標(biāo)相同的點(diǎn)，一類斜率點(diǎn)

3、考慮不周，點(diǎn)的坐標(biāo)可正可負(fù)，還想著用數(shù)組下標(biāo)保存，有點(diǎn)蠢

4、思路半路夭折，看了別人的思路。

int maxPoints(vector<Point> &points) {int n = points.size();if (n == 0) return 0;int maxNum = INT_MIN;map<int, vector<Point>> k;set<int> kindK;int shu[10005] = {0}; //shu[i]表示縱坐標(biāo)相同是i的點(diǎn)的個(gè)數(shù)int heng[10005] = {0}; //heng[i]表示橫坐標(biāo)相同是i的點(diǎn)的個(gè)數(shù)int maxX = INT_MIN, maxY = INT_MIN;int minX = INT_MAX, minY = INT_MAX;for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {int ix = points[i].x, iy = points[i].y;maxX = max(ix, maxX);minX = min(ix, minX);maxY = max(maxY, iy);minY = min(iy,minY);int jx = points[j].x, jy = points[j].y;maxX = max(jx, maxX);minX = min(jx, minX);maxY = max(maxY, jy);minY = min(jy,minY);if (ix == jx) { //在一條豎線上，橫坐標(biāo)相同heng[ix]++;} else if (iy == jy) {shu[iy]++;} else {int xie = (jy - iy) / (jx - ix);kindK.insert(xie);vector<Point> tmp;tmp = k[xie];tmp.push_back(points[i]);tmp.push_back(points[j]);k[xie] = tmp;}}}for(int i = minX; i <= maxX; i++){if(heng[i] == 0) continue;else{maxNum = max(maxNum, heng[i]);}}for(int i = minY; i <= maxY; i++){if(shu[i] == 0) continue;else{maxNum = max(maxNum, shu[i]);}}for(auto x : kindK){vector<Point> tmp = k[x];int b[10005] = {0};int maxB = INT_MIN;for(int i = 0; i < tmp.size(); i++){int bb = tmp[i].y - x*tmp[i].x;b[bb]++;maxB = max(bb,maxB);}for(int i = 0; i <= maxB; i++)}}

?

牛客網(wǎng)友的思路：

1.分兩層循環(huán)枚舉，第一遍遍歷起始點(diǎn)a，第二遍遍歷剩下的點(diǎn)

2.分兩類，垂直和有斜率的，要注意計(jì)算垂直點(diǎn)不為0時(shí)，不能重復(fù)計(jì)算

鏈接：https://www.nowcoder.com/questionTerminal/bfc691e0100441cdb8ec153f32540be2?f=discussion 來源：牛客網(wǎng)/*** Definition for a point.* struct Point {* int x;* int y;* Point() : x(0), y(0) {}* Point(int a, int b) : x(a), y(b) {}* };*/ class Solution { public:int maxPoints(vector<Point> &points) {int size = points.size();if(size == 0)return 0;else if(size == 1)return 1;int ret = 0;for(int i = 0;i<size;i++){int curmax = 1;map<double,int>mp;int vcnt = 0; //垂直點(diǎn)int dup = 0; //重復(fù)點(diǎn)for(int j = 0;j<size;j++){if(j!=i){double x1 = points[i].x - points[j].x;double y1 = points[i].y - points[j].y;if(x1 == 0 && y1 == 0){ //重復(fù)dup++;}else if(x1 == 0){ //垂直if(vcnt == 0)vcnt = 2;elsevcnt++;curmax = max(vcnt,curmax);}else{double k = y1/x1; //斜率if(mp[k] == 0)mp[k] = 2;elsemp[k]++;curmax = max(mp[k],curmax);} }}ret = max(ret,curmax+dup); }return ret;} };

?

超強(qiáng)干貨來襲 云風(fēng)專訪：近40年碼齡，通宵達(dá)旦的技術(shù)人生

總結(jié)

以上是生活随笔為你收集整理的牛客 -- leetcode -- max-points-on-a-line的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。