【学习报告】《LeetCode零基础指南》（第五讲）排序API

一、今日知识点总结：

• 学会了运用C语言中提供的排序API: qsort 进行排序 *** 作
• 学会了编写qsort的比较函数

---

二、今日做题记录： 1. 排序数组

int cmp(const void*a, const void* b) {
    return *(int *)a - *(int *)b;
}
int* sortArray(int* nums, int numsSize, int* returnSize){
    qsort(nums, numsSize, sizeof(int), cmp);
    *returnSize = numsSize;
    return nums;
}

2. 多数元素

int cmp(const void *a, const void *b) {
    return (*(int *)a) - (*(int *)b);
}
int majorityElement(int* nums, int numsSize){
    qsort(nums, numsSize, sizeof(int), cmp);
    return nums[numsSize/2];
}

3. 存在重复元素

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

bool containsDuplicate(int* nums, int numsSize){
    int i;
    qsort(nums, numsSize, sizeof(int), cmp);
    for(i = 1; i < numsSize; ++i) {
        if(nums[i] == nums[i-1]) {
            return true;
        }
    }
    return false;
}

4. 最大间距

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

int maximumGap(int* nums, int numsSize){
    int i, max = 0;
    qsort(nums, numsSize, sizeof(int), cmp);
    for(i = 1; i < numsSize; ++i) {
        if(nums[i] - nums[i-1] > max) {
            max = nums[i] - nums[i-1];
        }
    }
    return max;
}

5. 按奇偶排序数组

int Qua(int x) {
    return x & 1;
}

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

int* sortArrayByParity(int* nums, int numsSize, int* returnSize){
    int i;
    int *ret = (int *)malloc( sizeof(int) * numsSize );
    for(i = 0; i < numsSize; ++i) {
        ret[i] = nums[i];
    }
    qsort(ret, numsSize, sizeof(int), cmp);
    *returnSize = numsSize;
    return ret;
}

6. 最小时间差

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

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

int findMinDifference(char ** timePoints, int timePointsSize){
    int *ret = (int *) malloc( sizeof(int) * timePointsSize );
    int i, ans = 1440;
    int a, b;
    for(i = 0; i < timePointsSize; ++i) {
        sscanf(timePoints[i], "%d:%d", &a, &b);
        ret[i] = a * 60 + b;
    }
    qsort(ret, timePointsSize, sizeof(int), cmp);
    for(i = 1; i < timePointsSize; ++i) {
        ans = min(ans, ret[i] - ret[i-1]);
    }
    ans = min(ans, ret[0] - ret[timePointsSize-1] + 1440);
    return ans;
}

7. 三角形的最大周长

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

int largestPerimeter(int* nums, int numsSize){
    int i;
    qsort(nums, numsSize, sizeof(int), cmp);
    for(i = numsSize-1; i >= 2; --i) {
        if(nums[i-2] + nums[i-1] > nums[i]) {
            return nums[i-2] + nums[i-1] + nums[i];
        }
    }
    return 0;
}

8. 救生艇

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

int numRescueBoats(int* people, int peopleSize, int limit){
    int i;
    int l = 0, r = peopleSize-1;
    int ans = 0;
    qsort(people, peopleSize, sizeof(int), cmp);
    while(l <= r) {
        if(l == r) {
            ++ans; break;
        } else if(people[l] + people[r] > limit) {
            ++ans, r--;
        } else
            ++ans, ++l, --r;
    }
    return ans;
}