众数算法及其时间复杂度

众数算法是指在一个数列中出现次数最多的数。常用的众数算法有以下几种：

1. 哈希表法：遍历数列，使用哈希表统计每个数出现的次数，最后找到出现次数最多的数。时间复杂度为O(n)，空间复杂度为O(n)。

2. 排序法：将数列排序，出现次数最多的数必然在中间位置或者连续的一段位置上。时间复杂度为O(nlogn)，空间复杂度为O(1)。

3. 摩尔投票法：遍历数列，维护一个候选众数和它出现的次数，如果遍历到的数与候选众数相同，则将其出现次数加1，否则将其出现次数减1。当出现次数为0时，选择当前遍历到的数作为新的候选众数。时间复杂度为O(n)，空间复杂度为O(1)。

以上是常用的众数算法及其时间复杂度。

相关问题

用C举例从一数组内取众数算法

对于一个整型数组，我们可以使用计数排序的思想来求出众数。

具体操作如下：

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)。

在一个数组中出现次数最多的数称为众数。用分治法设计求解众数问题的算法，并分析时间复杂度

分治法求解众数问题的基本思路是将原问题分解成若干个子问题，然后将子问题的解合并起来得到原问题的解。具体实现时，可以将数组分成两个部分，分别求出左半部分和右半部分的众数，然后再将左右两个部分的众数进行比较，得到整个数组的众数。

算法步骤如下：

1. 将原数组分成左右两部分，分别求出左半部分和右半部分的众数。

2. 如果左半部分和右半部分的众数相同，则直接返回该众数。

3. 如果左半部分和右半部分的众数不同，则需要统计左半部分和右半部分各自出现次数最多的数，然后比较哪个出现次数更多，返回出现次数更多的数。

4. 如果左半部分或右半部分不存在众数，则需要统计整个数组中出现次数最多的数，返回该数。

时间复杂度分析：

假设数组长度为n，每次将数组分成两半，因此递归树的高度为logn。每一层递归需要进行两次统计众数的操作，每次的时间复杂度为O(n)，因此总的时间复杂度为O(nlogn)。