高效统计X、Y坐标均更大的2D点数量的算法优化求助

Key Insight #

Since all Y coordinates are unique, we can reduce the 2D problem to a 1D problem with these steps:

1. Sort points by Y in increasing order: This guarantees that any point appearing after another in the sorted list has a larger Y value.
2. Count valid X values with modified merge sort: For each point, we need to count how many subsequent points have an X value ≥ current X + minXDiff. Merge sort allows us to compute this efficiently in O(n log n) time by leveraging sorted subarrays during the merge phase.

How the Modified Merge Sort Works #

• Recursive Split: Split the sorted-by-Y array into left and right subarrays.
• Merge Phase:
  • For each element in the left subarray, use a two-pointer technique to count elements in the right subarray that meet the X condition. Since both subarrays are sorted by X, we can find the first valid element in the right subarray and calculate the count in linear time.
  • Merge the subarrays while maintaining sorted order by X to enable efficient counting in higher recursive levels.

Constructive Feedback on Your Original Code #

1. O(n²) Time Complexity: The backtracking loop in mergeAndCount checks every previous element for each new element added, leading to quadratic time. This negates merge sort's O(n log n) advantage.
2. Unnecessary Flag: The isAtRightSide flag is a workaround for double-counting, but it's redundant in the optimized approach where we explicitly count only valid cross-subarray contributions once.
3. Misaligned Merge Sort Usage: Sorting by Y during merge sort doesn't leverage the merge step for efficient counting. Instead, sort by Y first, then use merge sort on X to count valid elements.
4. VLA Risk: Variable-length arrays (e.g., Point *L[n1]) can cause stack overflow for large n. Use dynamic allocation instead.

Optimized Code Implementation #

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

typedef struct {
    int x;
    int y;
    int count;
} Point;

int compareByY(const void *a, const void *b) {
    Point *p1 = *(Point**)a;
    Point *p2 = *(Point**)b;
    return p1->y - p2->y;
}

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

    Point **L = malloc(n1 * sizeof(Point*));
    Point **R = malloc(n2 * sizeof(Point*));

    for (int i = 0; i < n1; i++) {
        L[i] = arr[l + i];
    }
    for (int j = 0; j < n2; j++) {
        R[j] = arr[m + 1 + j];
    }

    // Calculate valid counts from right subarray for left elements
    int j = 0;
    for (int i = 0; i < n1; i++) {
        // Find first element in R where X meets the minXDiff condition
        while (j < n2 && R[j]->x < L[i]->x + minXDiff) {
            j++;
        }
        L[i]->count += (n2 - j);
    }

    // Merge L and R into arr sorted by X
    int i = 0, k = l;
    j = 0;
    while (i < n1 && j < n2) {
        if (L[i]->x <= R[j]->x) {
            arr[k++] = L[i++];
        } else {
            arr[k++] = R[j++];
        }
    }

    while (i < n1) {
        arr[k++] = L[i++];
    }
    while (j < n2) {
        arr[k++] = R[j++];
    }

    free(L);
    free(R);
}

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);
    }

    // Sort temp array by Y in increasing order
    qsort(temp, n, sizeof(Point*), compareByY);

    // Compute counts using modified merge sort
    mergeSortAndCount(temp, 0, n - 1, minXDiff);

    // Output counts in original input order
    for (int i = 0; i < n; i++) {
        printf("%d\n", points[i]->count);
    }

    // Cleanup allocated memory
    for (int i = 0; i < n; i++) {
        free(points[i]);
    }
    free(points);
    free(temp);

    return 0;
}

Explanation #

• Sorting by Y: Ensures all subsequent points have larger Y values, reducing the problem to counting valid X values.
• Two-pointer Counting: During merge, we efficiently count how many elements in the right subarray meet the X condition, adding this count to the left elements' totals.
• Dynamic Allocation: Avoids stack overflow from variable-length arrays and ensures portability across compilers.

内容的提问来源于stack exchange，提问作者petdomaa100