【题解】《算法零基础100讲》(第41讲) C语言 排序 API

文章目录

一. 排序API

  排序API就是是同C语言内置的函数qsort进行排序。

qsort的定义方式:

void qsort (void* base, size_t num, size_t size,
            int (*compar)(const void*,const void*));

base是指需要排序的数组;
num是数组的长度;
size是所需排序的数组的数据类型大小
cmpar是比较函数的地址;

代码如下:

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

int main(){
	int arr[] = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
	int arrSize = sizeof(arr) / sizeof(arr[0]);
	qsort(arr, arrSize, sizeof(int), cmp);
	for (int i = 0; i < arrSize; i++){
		printf("%d ", arr[i]);
	}
	putchar('\n');
	return 0;
}

二. 推荐专栏

《算法零基础100讲》(第41讲) C语言 排序 API

三. 相关练习

3.1 排序数组

题目链接:
912. 排序数组

我们直接用qsort排序

代码如下:

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

int* sortArray(int* nums, int numsSize, int* returnSize){
    *returnSize = numsSize;
    qsort(nums, numsSize, sizeof(int), cmp);
    return nums;
}

3.2 多数元素

题目链接:

169. 多数元素

思路分析:

出现次数大于n/2的元素,我们将数组排好序后,假设出现次数最大的数为m,不管m是从第一个开始,还是从其他地方,因为它的数量大于n/2,所以nums[n / 2]一定为m。

代码如下:

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

int majorityElement(int* nums, int numsSize){
    qsort(nums, numsSize, sizeof(int), cmp);
    return nums[numsSize / 2];
}

3.3 存在重复元素

题目链接:

217. 存在重复元素

思路分析:

要判断一个数组有没有重复元素,排序就是一个很简单的办法,排好序后,相同的元素相邻,直接遍历判断相邻的元素即可。

代码如下:

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

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

3.4 最大间距

题目链接:

164. 最大间距

思路分析:

我们用qsort对其排好序,然后再找出相邻之间最大的差值。

代码如下:

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

3.5 按奇偶排序数组

题目链接:

905. 按奇偶排序数组

思路分析:

我们按照规则写cmp函数即可,偶数在前,奇数在后。

代码如下:

int cmp(int* a, int* b){
    if(*a % 2){//a为奇数
        if(*b % 2){//b也为奇数
            return *a - *b;
        }
        return 1;//偶数在前
    }
    else{
        if(*b % 2){
            return -1;
        }
        return *a > *b;
    }
}

int* sortArrayByParity(int* nums, int numsSize, int* returnSize){
    qsort(nums, numsSize, sizeof(int), cmp);
    *returnSize = numsSize;
    return nums;
}
上一篇:C++的字符串


下一篇:单例设计模式(&饿汉式 &懒汉式)