用C举例从一数组内取众数算法
时间: 2023-05-31 15:07:36 浏览: 103
对于一个整型数组,我们可以使用计数排序的思想来求出众数。
具体操作如下:
1. 对于数组进行升序(或降序)排序。
2. 定义一个变量temp记录出现次数最多的元素,以及一个变量count记录该元素的出现次数。
3. 从前往后遍历数组,用一个循环变量i遍历整个数组。当遇到相同元素时,count加一;当遇到不同元素时,判断count是否大于当前最大出现次数,若是,则更新temp和count;否则,继续向后遍历。
4. 循环结束后,temp即为所求的众数,返回temp即可。
示例代码:
int majorityElement(int* nums, int numsSize){
int temp, count=0;
qsort(nums, numsSize, sizeof(int), cmp);
temp = nums[0];
for(int i=1; i<numsSize; i++){
if(nums[i] == temp){
count++;
}else{
if(count > numsSize/2) break;
temp = nums[i];
count = 1;
}
}
return temp;
}
其中,cmp是排序函数,可以写成如下形式:
int cmp(const void* a, const void* b){
return *(int*)a - *(int*)b;
}
该算法的时间复杂度是O(nlogn),主要是因为排序的时间复杂度是O(nlogn),空间复杂度是O(1)。