首页 > itarticle > PU Kth Smallest Element in a Sorted Matrix

PU Kth Smallest Element in a Sorted Matrix

admin 11月 12, 2020 0

Jan 01, 1970

Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.

it is the kth smallest element in the sorted order, not the kth distinct element.
You may assume k is always valid, 1 ≤ k ≤ n2.

Example:

matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
],
k = 8,
return 13.

C Solution:

struct Heap {
    int top;
    int size;
    int *vals;
    int *r;
    int *c;
};
struct Heap *create() {
    struct Heap *obj = malloc(sizeof(struct Heap));
    obj->size = 1000;
    obj->top = 1;
    obj->vals = malloc(obj->size * sizeof(int));
    obj->r = malloc(obj->size * sizeof(int));
    obj->c = malloc(obj->size * sizeof(int));
    return obj;
}
void pop(struct Heap *heap, int *r, int *c) {
    *r = heap->r[1];
    *c = heap->c[1];
    heap->vals[1] = heap->vals[--heap->top];
    heap->r[1] = heap->r[heap->top];
    heap->c[1] = heap->c[heap->top];
    int root = 1, left = 2;
    while (left < heap->top) {
        int target = left, right = left + 1;
        if (right < heap->top && heap->vals[right] < heap->vals[left]) target = right;
        if (heap->vals[root] <= heap->vals[target]) return;
        int tmp = heap->vals[root];
        heap->vals[root] = heap->vals[target];
        heap->vals[target] = tmp;

        tmp = heap->r[root];
        heap->r[root] = heap->r[target];
        heap->r[target] = tmp;

        tmp = heap->c[root];
        heap->c[root] = heap->c[target];
        heap->c[target] = tmp;

        root = target;
        left = root * 2;
    }
}
void push(struct Heap *heap, int val, int r, int c) {
    if (heap->size == heap->top) {
        heap->size += 1000;
        heap->vals = realloc(heap->vals, heap->size * sizeof(int));
        heap->r = realloc(heap->r, heap->size * sizeof(int));
        heap->r = realloc(heap->c, heap->size * sizeof(int));
    }
    heap->vals[heap->top] = val;
    heap->r[heap->top] = r;
    heap->c[heap->top] = c;
    int cur = heap->top++, root = cur / 2;
    while (root && heap->vals[root] > heap->vals[cur]) {
        int tmp = heap->vals[root];
        heap->vals[root] = heap->vals[cur];
        heap->vals[cur] = tmp;

        tmp = heap->r[root];
        heap->r[root] = heap->r[cur];
        heap->r[cur] = tmp;

        tmp = heap->c[root];
        heap->c[root] = heap->c[cur];
        heap->c[cur] = tmp;

        cur = root;
        root = cur / 2;
    }
}
int kthSmallest(int** matrix, int matrixRowSize, int matrixColSize, int k) {
    struct Heap *heap = create();
    push(heap, matrix[0][0], 0, 0);
    int r, c, i;
    for (i = 0; i < k; i++) {
        pop(heap, &r, &c);
        if (r < matrixRowSize - 1) push(heap, matrix[r + 1][c], r + 1, c);
        if (!r && c < matrixColSize - 1) push(heap, matrix[r][c + 1], r , c + 1);
    }
    return matrix[r][c];
}

Summary:

16ms, 81.25%
Similar to the privious problem.
Using binary search could be a better choice here, because what we are doing is to search one element, rather than a part.

LeetCode: 378. Kth Smallest Element in a Sorted Matrix