Medium

题目描述

给你一个大小为 n x 2 的二维数组 points，表示二维平面上一些点的整数坐标，其中 points[i] = [xi, yi]。

统计满足以下条件的点对 (A, B) 的数量：

  • A 在 B 的左上方，并且
  • 在它们构成的矩形（或直线）中没有其他点（包括边界），除了点 A 和 B。

返回满足条件的点对数量。

示例 1：

输入：points = [[1,1],[2,2],[3,3]]
输出：0
解释：没有办法选择 A 和 B 使得 A 在 B 的左上方。

示例 2：

输入：points = [[6,2],[4,4],[2,6]]
输出：2
解释：
- 左边的点对是 (points[1], points[0])，其中 points[1] 在 points[0] 的左上方且矩形为空。
- 中间的点对是 (points[2], points[1])，与左边的情况相同，是有效的点对。
- 右边的点对是 (points[2], points[0])，其中 points[2] 在 points[0] 的左上方，但 points[1] 在矩形内部，所以不是有效的点对。

示例 3：

输入：points = [[3,1],[1,3],[1,1]]
输出：2
解释：
- 左边的点对是 (points[2], points[0])，其中 points[2] 在 points[0] 的左上方且它们形成的直线上没有其他点。注意当两个点形成一条直线时也是有效状态。
- 中间的点对是 (points[1], points[2])，与左边的情况相同，是有效的点对。
- 右边的点对是 (points[1], points[0])，由于 points[2] 在矩形的边界上，所以不是有效的点对。

提示：

  • 2 <= n <= 50
  • points[i].length == 2
  • 0 <= points[i][0], points[i][1] <= 50
  • 所有 points[i] 都是不同的。

解题思路

解题思路

这道题需要找到所有满足条件的点对 (A, B)，其中 A 在 B 的左上方，且它们构成的矩形区域内没有其他点。

核心思路：

  1. 枚举所有点对：对于每对点 (A, B)，检查是否满足 A 在 B 的左上方，即 A.x ≤ B.x 且 A.y ≥ B.y。

  2. 检查矩形区域：对于每个有效的点对，需要检查由这两个点构成的矩形区域内是否存在其他点。矩形的边界为：

    • 左边界：min(A.x, B.x)
    • 右边界：max(A.x, B.x)
    • 下边界：min(A.y, B.y)
    • 上边界：max(A.y, B.y)

  3. 验证空矩形：对于每个其他点 C，检查是否满足：

    • min(A.x, B.x) ≤ C.x ≤ max(A.x, B.x)
    • min(A.y, B.y) ≤ C.y ≤ max(A.y, B.y)

如果矩形内存在其他点（除了 A 和 B），则该点对无效。

算法复杂度：

  • 时间复杂度：O(n³)，其中 n 是点的数量
  • 空间复杂度：O(1)

由于题目约束 n ≤ 50，暴力枚举的方法是完全可行的。

代码实现

class Solution {
public:
    int numberOfPairs(vector<vector<int>>& points) {
        int n = points.size();
        int count = 0;
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                
                int x1 = points[i][0], y1 = points[i][1];
                int x2 = points[j][0], y2 = points[j][1];
                
                // Check if point i is upper-left of point j
                if (x1 <= x2 && y1 >= y2) {
                    bool valid = true;
                    
                    // Check if any other point is inside the rectangle
                    for (int k = 0; k < n; k++) {
                        if (k == i || k == j) continue;
                        
                        int x = points[k][0], y = points[k][1];
                        if (x >= x1 && x <= x2 && y >= y2 && y <= y1) {
                            valid = false;
                            break;
                        }
                    }
                    
                    if (valid) count++;
                }
            }
        }
        
        return count;
    }
};

class Solution:
    def numberOfPairs(self, points: List[List[int]]) -> int:
        n = len(points)
        count = 0
        
        for i in range(n):
            for j in range(n):
                if i == j:
                    continue
                
                x1, y1 = points[i]
                x2, y2 = points[j]
                
                # Check if point i is upper-left of point j
                if x1 <= x2 and y1 >= y2:
                    valid = True
                    
                    # Check if any other point is inside the rectangle
                    for k in range(n):
                        if k == i or k == j:
                            continue
                        
                        x, y = points[k]
                        if x1 <= x <= x2 and y2 <= y <= y1:
                            valid = False
                            break
                    
                    if valid:
                        count += 1
        
        return count

public class Solution {
    public int NumberOfPairs(int[][] points) {
        int n = points.Length;
        int count = 0;
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                
                int x1 = points[i][0], y1 = points[i][1];
                int x2 = points[j][0], y2 = points[j][1];
                
                // Check if point i is upper-left of point j
                if (x1 <= x2 && y1 >= y2) {
                    bool valid = true;
                    
                    // Check if any other point is inside the rectangle
                    for (int k = 0; k < n; k++) {
                        if (k == i || k == j) continue;
                        
                        int x = points[k][0], y = points[k][1];
                        if (x >= x1 && x <= x2 && y >= y2 && y <= y1) {
                            valid = false;
                            break;
                        }
                    }
                    
                    if (valid) count++;
                }
            }
        }
        
        return count;
    }
}

var numberOfPairs = function(points) {
    let count = 0;
    const n = points.length;
    
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            if (i === j) continue;
            
            const [x1, y1] = points[i];
            const [x2, y2] = points[j];
            
            // Check if A is upper left of B
            if (x1 <= x2 && y1 >= y2) {
                let valid = true;
                
                // Check if any other point is in the rectangle
                for (let k = 0; k < n; k++) {
                    if (k === i || k === j) continue;
                    
                    const [x3, y3] = points[k];
                    
                    // Check if point k is inside or on the boundary of rectangle
                    if (x3 >= x1 && x3 <= x2 && y3 <= y1 && y3 >= y2) {
                        valid = false;
                        break;
                    }
                }
                
                if (valid) count++;
            }
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n³)
空间复杂度O(1)

相关题目