高效统计X轴和Y轴坐标较高的2D点的数量

Question

我是一名大学生，正在完成高级算法课程的作业。

简单来说任务：
我得到了一个二维点数组。对于每个点，我需要显示具有更大 X 和 Y 坐标的其他点的数量。对于每个点，Y 坐标都是唯一的。

本次作业给出的提示是“归并排序”。经过一番谷歌搜索后，我看到了一些关于反转计数的内容，但我无法将其应用于 2D 点。

相反，我构建了一种不同的算法：
按

y

坐标进行合并排序。每次在合并过程中添加元素时，都会回溯已添加的元素，并增加每个具有较低

x

坐标的元素的计数。

它工作得很好，它给了我正确的输出，但是这种回溯方法效率很低，并且随着

n

变大而需要很长时间。这并不比使用 2 个嵌套循环更好。不幸的是，这是我能想到的唯一围绕合并排序构建的东西。

我正在寻找可以加快我的代码速度的想法。预先感谢。

这是我的算法：

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int x;
    int y;
    int count;
    int isAtRightSide; // Only used during mergeAndCount
} Point;

void mergeAndCount(Point *arr[], int l, int m, int r, int minXDiff) {
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;

    Point *L[n1];
    Point *R[n2];

    for (i = 0; i < n1; i++) {
        L[i] = arr[l + i];
        L[i]->isAtRightSide = 0;
    }

    for (j = 0; j < n2; j++) {
        R[j] = arr[m + 1 + j];
        R[j]->isAtRightSide = 1;
    }

    // ==========

    i = 0;
    j = 0;
    k = l;

    while (i < n1 || j < n2) {
        if (i < n1 && j < n2) {
            if (L[i]->y <= R[j]->y) {
                arr[k] = L[i++];
            } else {
                arr[k] = R[j++];
            }
        } else if (i < n1) {
            arr[k] = L[i++];
        } else {
            arr[k] = R[j++];
        }

        for (int o = k - 1; o >= l; o--) {
            if (
                arr[o]->x + minXDiff <= arr[k]->x &&
                arr[o]->isAtRightSide != arr[k]->isAtRightSide // Same side already has it counted
            ) {
                arr[o]->count++;
            }
        }

        k++;
    }
}

void mergeSortAndCount(Point *arr[], int l, int r, int minXDiff) {
    if (l < r) {
        int m = l + (r - l) / 2;

        mergeSortAndCount(arr, l, m, minXDiff);
        mergeSortAndCount(arr, m + 1, r, minXDiff);

        mergeAndCount(arr, l, m, r, minXDiff);
    }
}

int main() {
    int n, minXDiff;

    scanf("%d %d", &n, &minXDiff);

    Point **points = malloc(n * sizeof(Point*));
    Point **temp = malloc(n * sizeof(Point*));

    for (int i = 0; i < n; i++) {
        points[i] = temp[i] = malloc(sizeof(Point));
        points[i]->count = 0;

        scanf("%d %d", &points[i]->x, &points[i]->y);
    }

    // ====================

    mergeSortAndCount(temp, 0, n - 1, minXDiff);

    for (int i = 0; i < n; i++) {
        printf("%d\n", points[i]->count);
    }

    // ====================

    for (int i = 0; i < n; i++) {
        free(points[i]);
    }

    free(points);
    free(temp);

    return 0;
}

我也希望对我在这里所做的事情提出建设性的批评。

Answer 1

这是提示的解释。

首先按

y

排序。

通过

x

进行合并排序，通过从第二个列表中取出它们来打破平局。每次合并第一个列表中的元素时，找到刚刚找到的具有较高

x

和

y

的点的有效方法是什么？

注意，

y

不同的条件很重要。