一、环境说明

1. 本文是 LeetCode 1337题 :矩阵中战斗力最弱的 K 行,使用c语言实现
2. 测试环境:Visual Studio 2019

二、代码展示

int cmp(const void* _a, const void* _b)
{
    int* a = (int*)_a;
    int* b = (int*)_b;
    return a[0] > b[0];
}
int binary_search(int* arr, int len) {//二分查找,返回战斗力
    int left = 0, right = len - 1, mid = 0;
    while (left<=right)
    {
        mid = (left + right) >> 1;
        if (arr[mid]) {//arr[mid]是军人
            left = mid + 1;
        }
        if (0 == arr[mid]) {//arr[mid]是平民
            right = mid - 1;
        }
    }
    return left;
}
int* kWeakestRows(int** mat, int matSize, int* matColSize, int k, int* returnSize) {
    *returnSize = k;
    int m = *matColSize;//每行元素个数
    int n = matSize;//行数
    int temp[100][2] = { 0 };//每一行0存放战斗力,1存放行号
    for (int i = 0; i < n; i++) {//遍历每一行
        temp[i][0] = binary_search(mat[i], m);
        temp[i][1] = i;
    }
    qsort(temp, matSize, sizeof(int*), cmp);
    int* answer = (int*)calloc(k, sizeof(int));
    for (int i = 0; i < k; i++) {
        answer[i] = temp[i][1];
    }
    return answer;
}

三、代码分析

1. 初刷本题，一定要知道，形参和题目的对应关系。因为题目描述里，没有解释这些参数，所以直接看答案效率更高。
2. 整体思路：建立一个二维数组100行，2列。数组每行对应矩阵的一行。列是属性，第0列是战斗力，第1列是行号。通过二分查找，获得战斗力，同时存入行号。再对矩阵按行排序，按战斗力升序。
3. 常见问题：①数组有100行，这个行数是最大行数，不一定全用。②由于矩阵按行序存入，战斗力相同的两行天然有序，快拍后他们仍然有序。
4. cmp()是一个排序规则函数，服务于qsort()库函数。
5. binary_search()是二分查找，比for循环更快。时间复杂度是log₂m，m是每行元素个数,

四、AC

五、复杂度分析

1. 时间复杂度:O(nlog₂m + nlog₂n) ,n是行数，m是列数。nlog₂m是二分查找的时间复杂度，nlog₂n是快速排序的时间复杂度。
2. 空间复杂度:O(|C|+k）因为使用了对应题目限制，最大长度的数组，所以C就是最大长度，即C=100*2。k是需要返回的数组长度。
3. 改进空间复杂度方案:创建结构体，存战斗力和行号，动态申请n大小的结构体指针。这样一来，C可以减少为2n。

引用链接:
https://blog.csdn.net/lingjinyue/article/details/108932736?ops_request_misc=&request_id=&biz_id=102&utm_term=leetcode%201337%20c&utm_medium=distribute.pc_search_result.none-task-blog-2_allsobaiduweb~default-0-108932736.142^v51control_1,201^v3control_2&spm=1018.2226.3001.4187
被引用文章的作者，使用了qsort()，值得学习