diff options
author | Jack Sangdahl <[email protected]> | 2025-02-17 00:05:42 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-02-17 00:05:42 -0700 |
commit | 53cc13f027ba1935213ee2564a72eaab49db5b43 (patch) | |
tree | c7c914ab0220c07755d41a8ec19d39cc44fe0107 /k_closest_points_origin.c | |
parent | 3164a692e8f47404f9a50f0e09a4bfe16351f15d (diff) | |
download | leetcode-53cc13f027ba1935213ee2564a72eaab49db5b43.tar.gz leetcode-53cc13f027ba1935213ee2564a72eaab49db5b43.zip |
973. k closest points to origin
Diffstat (limited to 'k_closest_points_origin.c')
-rw-r--r-- | k_closest_points_origin.c | 119 |
1 files changed, 119 insertions, 0 deletions
diff --git a/k_closest_points_origin.c b/k_closest_points_origin.c new file mode 100644 index 0000000..b0c2a51 --- /dev/null +++ b/k_closest_points_origin.c @@ -0,0 +1,119 @@ +// 973. K Closest Points to Origin +#include "leetcode.h" + +/* + * given an array of 'points' where 'points[i] = [x_i, y_i]' represents a point + * on the x-y plane and an integer 'k', return the 'k' closest points to the + * origin '(0, 0)'. the distance between two points on the x-y plane is the + * euclidean distance (ie. 'sqrt((x1 - x2)^2 + (y1 - y2)^2))'. you may return + * the answer in any order. the answer is guaranteed to be unique (except for + * the order that it is in). + */ + +struct node { + int x; + int y; + int dist; +}; + +void swap(struct node *a, struct node *b) { + struct node tmp = *a; + *a = *b; + *b = tmp; +} + +void heapify(struct node *heap, int size, int i) { + int largest = i, left = 2 * i + 1, right = 2 * i + 2; + if (left < size && heap[left].dist > heap[largest].dist) + largest = left; + if (right < size && heap[right].dist > heap[largest].dist) + largest = right; + if (largest != i) { + swap(&heap[i], &heap[largest]); + heapify(heap, size, largest); + } +} + +void heap_push(struct node *heap, int *size, struct node n) { + heap[*size] = n; + int i = *size; + (*size)++; + while (i && heap[(i - 1) / 2].dist < heap[i].dist) { + swap(&heap[i], &heap[(i - 1) / 2]); + i = (i - 1) / 2; + } +} + +struct node get_max(struct node *heap, int *size) { + struct node max = heap[0]; + heap[0] = heap[*size - 1]; + (*size)--; + heapify(heap, *size, 0); + return max; +} + +int **kClosest(int **points, int pointsSize, int *pointsColSize, int k, + int *returnSize, int **returnColumnSizes) { + struct node *max_heap = (struct node *)malloc(k * sizeof(struct node)); + int heap_size = 0; + for (int i = 0; i < k; i++) { + struct node n; + n.x = points[i][0]; + n.y = points[i][1]; + n.dist = n.x * n.x + n.y * n.y; + heap_push(max_heap, &heap_size, n); + } + for (int i = k; i < pointsSize; i++) { + struct node n; + n.x = points[i][0]; + n.y = points[i][1]; + n.dist = n.x * n.x + n.y * n.y; + if (n.dist < max_heap[0].dist) { + get_max(max_heap, &heap_size); + heap_push(max_heap, &heap_size, n); + } + } + *returnSize = k; + *returnColumnSizes = (int *)malloc(k * sizeof(int)); + int **ans = (int **)malloc(k * sizeof(int *)); + for (int i = 0; i < k; i++) { + ans[i] = (int *)malloc(2 * sizeof(int)); + ans[i][0] = max_heap[i].x; + ans[i][1] = max_heap[i].y; + (*returnColumnSizes)[i] = 2; + } + free(max_heap); + return ans; +} + +int main() { + int p1i[2][2] = {{1, 3}, {-2, 2}}, p2i[3][2] = {{3, 3}, {5, -1}, {-2, 4}}; + struct two_d_arr p1, p2; + two_d_arr_init(&p1, ARRAY_SIZE(p1i), ARRAY_SIZE(p1i[0]), p1i); + two_d_arr_init(&p2, ARRAY_SIZE(p2i), ARRAY_SIZE(p2i[0]), p2i); + int rs1, rs2, *rcs1, *rcs2; + int **kc1 = kClosest(p1.arr, p1.row_size, p1.col_size, 1, &rs1, &rcs1); + int **kc2 = kClosest(p2.arr, p2.row_size, p2.col_size, 2, &rs2, &rcs2); + for (int i = 0; i < rs1; i++) { + for (int j = 0; j < rcs1[i]; j++) + printf("%d ", kc1[i][j]); // expect: [[-2,2]] + printf("\n"); + } + printf("\n"); + for (int i = 0; i < rs2; i++) { + for (int j = 0; j < rcs2[i]; j++) + printf("%d ", kc2[i][j]); // expect: [[3,3],[-2,4]] + printf("\n"); + } + printf("\n"); + for (int i = 0; i < rs1; i++) + free(kc1); + free(kc1); + free(rcs1); + two_d_arr_free(&p1); + for (int i = 0; i < rs2; i++) + free(kc2); + free(kc2); + free(rcs2); + two_d_arr_free(&p2); +} |