说在前面
🎈不知道大家对于算法的学习是一个怎样的心态呢？为了面试还是因为兴趣？不管是出于什么原因，算法学习需要持续保持。
题目描述
给你一个 n x 2 的二维数组 points ，它表示二维平面上的一些点坐标，其中 points[i] = [xi, yi] 。
我们定义 x 轴的正方向为 右 （x 轴递增的方向），x 轴的负方向为 左 （x 轴递减的方向）。类似的，我们定义 y 轴的正方向为 上 （y 轴递增的方向），y 轴的负方向为 下 （y 轴递减的方向）。
你需要安排这 n 个人的站位，这 n 个人中包括 liupengsay 和小羊肖恩 。你需要确保每个点处 恰好 有 一个 人。同时，liupengsay 想跟小羊肖恩单独玩耍，所以 liupengsay 会以 liupengsay ****的坐标为 左上角 ，小羊肖恩的坐标为 右下角 建立一个矩形的围栏（注意，围栏可能 不 包含任何区域，也就是说围栏可能是一条线段）。如果围栏的 内部 或者 边缘 上有任何其他人，liupengsay 都会难过。
请你在确保 liupengsay 不会 难过的前提下，返回 liupengsay 和小羊肖恩可以选择的 点对 数目。
注意，liupengsay 建立的围栏必须确保 liupengsay 的位置是矩形的左上角，小羊肖恩的位置是矩形的右下角。比方说，以 (1, 1) ，(1, 3) ，(3, 1) 和 (3, 3) 为矩形的四个角，给定下图的两个输入，liupengsay 都不能建立围栏，原因如下：
- 图一中，liupengsay 在
(3, 3)且小羊肖恩在(1, 1)，liupengsay 的位置不是左上角且小羊肖恩的位置不是右下角。 - 图二中，liupengsay 在
(1, 3)且小羊肖恩在(1, 1)，小羊肖恩的位置不是在围栏的右下角。
示例 1：
输入： points = [[1,1],[2,2],[3,3]] 输出： 0 解释： 没有办法可以让 liupengsay 的围栏以 liupengsay 的位置为左上角且小羊肖恩的位置为右下角。所以我们返回 0 。
示例 2：
输入： points = [[6,2],[4,4],[2,6]] 输出： 2 解释： 总共有 2 种方案安排 liupengsay 和小羊肖恩的位置，使得 liupengsay 不会难过： - liupengsay 站在 (4, 4) ，小羊肖恩站在 (6, 2) 。 - liupengsay 站在 (2, 6) ，小羊肖恩站在 (4, 4) 。 不能安排 liupengsay 站在 (2, 6) 且小羊肖恩站在 (6, 2) ，因为站在 (4, 4) 的人处于围栏内。
示例 3：
输入： points = [[3,1],[1,3],[1,1]] 输出： 2 解释： 总共有 2 种方案安排 liupengsay 和小羊肖恩的位置，使得 liupengsay 不会难过： - liupengsay 站在 (1, 1) ，小羊肖恩站在 (3, 1) 。 - liupengsay 站在 (1, 3) ，小羊肖恩站在 (1, 1) 。 不能安排 liupengsay 站在 (1, 3) 且小羊肖恩站在 (3, 1) ，因为站在 (1, 1) 的人处于围栏内。 注意围栏是可以不包含任何面积的，上图中第一和第二个围栏都是合法的。
提示：
2 <= n <= 50points[i].length == 20 <= points[i][0], points[i][1] <= 50points[i]点对两两不同。
解题思路
- 1、首先我们先对坐标集合进行排序，以左上到右下的顺序排
points = points.sort((a, b) => { if (a[0] === b[0]) return b[1] - a[1]; return a[0] - b[0]; });
- 2、编写一个检查函数，用于判断坐标集合中是否有某个坐标位于两个点围成的矩形中
const check = (ind1, ind2) => { const p1 = points[ind1], p2 = points[ind2]; if ((p1[1] !== p2[1] && p1[0] > p2[0]) || (p1[0] != p2[0] && p1[1] < p2[1])) return false; for (let i = 0; i < points.length; i++) { if (i === ind1 || i === ind2) continue; const p = points[i]; if (p1[0] <= p[0] && p2[0] >= p[0] && p1[1] >= p[1] && p2[1] <= p[1]) return false; } return true; };
- 3、枚举所有坐标组合进行判断，计算满足要求的坐标组合数
for (let i = 0; i < points.length; i++) { for (let j = i + 1; j < points.length; j++) { if (check(i, j)) { cnt++; } } }
1.首先，对 points 数组进行排序。排序规则是先按照元素的第一个值升序排序，如果第一个值相同，则按照第二个值降序排序。
2.初始化计数器 cnt 为 0。
3.定义了一个名为 check 的辅助函数，用于检查两个点是否满足特定条件。详细条件如下：
- 如果两个点的纵坐标不相等且第一个点的横坐标大于第二个点的横坐标，或者两个点的横坐标不相等且第一个点的纵坐标小于第二个点的纵坐标，则返回 false。
- 遍历除了这两个点之外的所有点，如果存在一个点落在这两个点所形成的矩形区域内，则返回 false。
- 如果以上条件都不满足，则返回 true。
4.使用两层循环遍历所有的点对，对每一对点调用 check 函数进行检查，如果满足条件，则将计数器 cnt 加一。
5.返回计数器 cnt 的值。
AC代码
/** * @param {number[][]} points * @return {number} */ var numberOfPairs = function (points) { points = points.sort((a, b) => { if (a[0] === b[0]) return b[1] - a[1]; return a[0] - b[0]; }); let cnt = 0; const check = (ind1, ind2) => { const p1 = points[ind1], p2 = points[ind2]; if ((p1[1] !== p2[1] && p1[0] > p2[0]) || (p1[0] != p2[0] && p1[1] < p2[1])) return false; for (let i = 0; i < points.length; i++) { if (i === ind1 || i === ind2) continue; const p = points[i]; if (p1[0] <= p[0] && p2[0] >= p[0] && p1[1] >= p[1] && p2[1] <= p[1]) return false; } return true; }; for (let i = 0; i < points.length; i++) { for (let j = i + 1; j < points.length; j++) { if (check(i, j)) { cnt++; } } } return cnt; };
公众号
关注公众号『前端也能这么有趣』，获取更多有趣内容。
说在后面
🎉 这里是 JYeontu，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打羽毛球 🏸 ，平时也喜欢写些东西，既为自己记录 📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解 🙇，写错的地方望指出，定会认真改进 😊，偶尔也会在自己的公众号『
前端也能这么有趣』发一些比较有趣的文章，有兴趣的也可以关注下。在此谢谢大家的支持，我们下文再见 🙌。
