Steward

分享是一種喜悅、更是一種幸福

程式語言 - LeetCode - C - 3567. Minimum Absolute Difference in Sliding Submatrix

---

參考資訊：
https://algo.monster/liteproblems/3567

題目：


解答：

int mysort(const void* a, const void* b)
{
    return (*(const int *)a) - (*(const int *)b);
}

int min(int a, int b)
{
    return a > b ? b : a;
}

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int** minAbsDiff(int** grid, int gridSize, int* gridColSize, int k, int* returnSize, int** returnColumnSizes)
{
    int i = 0;
    int j = 0;
    int row_size = gridSize;
    int col_size = gridColSize[0];
    int **ret = calloc(row_size, sizeof(int *));

    *returnColumnSizes = calloc(row_size, sizeof(int));
    for (i = 0; i < row_size; i++) {
        ret[i] = calloc(col_size, sizeof(int));
    }

    for (i = 0; i <= (row_size - k); i++) {
        for (j = 0; j <= (col_size - k); j++) {
            int m = 0;
            int ro = 0;
            int cl = 0;
            int q_cnt = 0;
            int q_buf[1024] = { 0 };

            for (ro = i; ro < (i + k); ro++) {
                for (cl = j; cl < (j + k); cl++) {
                    q_buf[q_cnt++] = grid[ro][cl];
                }
            }

            qsort(q_buf, q_cnt, sizeof(int), mysort);

            m = INT_MAX;
            for (ro = 1; ro < q_cnt; ro++) {
                int v = abs(q_buf[ro] - q_buf[ro - 1]);

                if (v > 0) {
                    m = min(m, v);
                }
            }
            ret[i][j] = (m == INT_MAX) ? 0 : m;
            (*returnColumnSizes)[i] = j + 1;
        }
        (*returnSize) = i + 1;
    }

    return ret;
}