当前位置：首页 > news >正文

【LeetCode刷题集】--排序（一）

news 2025/8/5 16:19:18

😘个人主页：@Cx330❀

👀个人简介：一个正在努力奋斗逆天改命的二本觉悟生

📖个人专栏：《C语言》《LeetCode刷题集》《数据结构-初阶》

前言：这是主播的第一篇LeetCode刷题集，这篇博客以及后续的博客都会带着大家刷题，由于考虑到大家的算法能力，刚开始会带着大家刷简单题，后续会慢慢加大难度，尝试一些中等难度的题，希望大家可以坚持到底，我们共同进步！

题目一：多数元素

题意：

思路：

代码实现：

复杂度分析：

qsort函数

概念：

参数及其原理：

cmp函数简单实现

题目二：存在重复元素

题意：

思路：

代码实现：

复杂度分析：

题目三：有效的字母异位词

题意：

思路：

代码实现：

复杂度分析：

题目一：多数元素

题目链接： 169.多数元素-力扣（LeetCode）

题意：

题目中给了一个大小为n数组nums，要求要返回在数组中出现次数大于n/2的元素。

思路：

“同归于尽消杀法” ：

由于多数超过50%, 比如100个数，那么多数至少51个，剩下少数是49个。

第一个到来的士兵，直接插上自己阵营的旗帜 flag = nums[i] 占领这块高地，现存兵力 flagnum= 1。

如果新来的士兵和前一个士兵是同一阵营，则集合起来占领高地，flag不变依然是当前这个士兵所属阵营，现存兵力 flagnum++；

如果新来到的士兵不是同一阵营，则当前 flag 阵营派一个士兵和它同归于尽。此时flag阵营兵力flagnum--。（即使双方都死光，这块高地的旗帜 flag 依然不变，因为已经没有活着的士兵可以去换上自己的新旗帜）

当下一个士兵到来，发现 flag 阵营已经没有兵力，则直接插上自己阵营的旗帜 flag = nums[i] 占领这块高地，现存兵力 flagnum++。

就这样各路军阀一直以这种以一敌一同归于尽的方式厮杀下去，直到少数阵营都死光，那么最后剩下的几个必然属于多数阵营，flag 就是多数阵营。

代码实现：

int majorityElement(int* nums, int numsSize) 
{int flag=nums[0];int flagnum=0;int i=0;while(i<numsSize){//同一个阵营兵力++if(nums[i]==flag){flagnum++;i++;}//没有兵力else{if(flagnum==0){flag=nums[i];i++;flagnum++;}//不同阵营else{flagnum--;i++;}}}return flag;
}

复杂度分析：

注：这里不讨论空间复杂度的情况了，通常情况下时间复杂度是影响通过的关键因素

时间复杂度：O(N)

如果大家对复杂度分析这块知识不是很清晰的话可以看一下我数据结构初阶的博客：

【数据结构初阶】--算法复杂度详解

qsort函数

概念：

qsort()函数是一个C语言编译器函数库自带的排序函数，它可以对指定数组（包括字符串，二维数组，结构体等）进行排序。

参数及其原理：

从cplusplus官网（cplusplus（C语言函数查询网站））上我们可以看到qsort()函数是有四个参数的，如图：

而cplusplus官网对这四个变量的解释是：

void*base ：qsort()函数需要的第一个参数是待排序数组的首元素地址，而void*的意思是它是一个无类型指针，而无类型的原因是我们希望它是一个可以排序很多种类数据的排序函数，如果这里的指针类型固定，我们就只能对函数传入固定类型的参数进行排序了。
size_t num:这个参数代表待排数组的元素个数。且因为元素个数恒为非负数，因此该参数的数据类型是size_t(即无符号整形)。
size_t size:这个参数代表待排数组的元素个数。且因为元素个数恒为非负数，因此该参数的数据类型是size_t(即无符号整形)。
compar:通常简写为cmp，经过我们的分析可知，该参数是一个函数指针，该指针指向的函数需要两个无类型的指针作为参数，同时该函数的返回值是一个int类型的整形。他的作用是将传进来的两个参数进行比较，如果参数p1<参数p2，则返回一个小于0的数，如果参数p1=参数p2,则返回0；如果参数p1>p2，则返回一个大于0的数。

cmp函数简单实现

int cmp(const void* a, const void* b) {

return *(int*)a -*(int*)b;

}

补充：*(int*)a -*(int*)b排序过后得到的是升序数组，若想要得到降序数组，把二者反过来即可：*(int*)b-*(int*)a

题目二：存在重复元素

题目链接： 217.存在重复元素-力扣（LeetCode）

题意：

题目中给了一个整数数组nums，如果任一值在数组中出现最少两次，返回true，否则返回false

思路：

qsort排序：

对原数组直接进行qsort排序，此时得到有序数组，判断数组相邻元素是否相等，如果相等则返回true，否则返回false

补充：qsort()函数是一个C语言编译器函数库自带的排序函数，它可以对指定数组（包括字符串，二维数组，结构体等）进行排序。

代码实现：

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

复杂度分析：

时间复杂度：O(NlogN)

题目三：有效的字母异位词

题目链接：242.有效的字母异位词-力扣（LeetCode）

题意：

给定两个字符串s和t，判断是否为异位次

异位词：两个字符串的元素种类及个数都相同，顺序不同

思路：

qsort排序s和t，strcmp比较s和t的字符种类以及个数即可。

如果大家对字符串函数（strcmp等）不太清楚的话可以看下我之前写的博客，帮助大家快速理解：

【C语言】：字符串函数超详解（10个最重要函数）

代码实现：

int cmp(const void*a,const void*b)
{return *(char*)a-*(char*)b;
}
bool isAnagram(char* s, char* t) 
{size_t ssize=strlen(s);size_t tsize=strlen(t);qsort(s,ssize,sizeof(char),cmp);qsort(t,tsize,sizeof(char),cmp);int flag=strcmp(s,t);if(flag==0){return true;}return false;
}