用分治法求解众数问题 给定一个整数序列,每个元素出现的次数为重数,重数最大的元素称为众数。编写一个程序对递增有序序列a求众数。例如 S={1, 2, ,2, 2, 3, 3, 5},多重集S的众数是2,其重数为3。 请描述算法设计思路,并给出算法核心代码。
时间: 2023-05-30 16:05:36 浏览: 550
算法设计思路:
1. 递归地将序列分成两个子序列,分别求出它们的众数;
2. 如果两个子序列的众数相同,则这个数就是整个序列的众数;
3. 如果两个子序列的众数不同,则分别计算它们在整个序列中出现的次数,返回出现次数较多的那个数作为整个序列的众数。
算法核心代码:
```
int findMode(int a[], int left, int right) {
if (left == right) {
return a[left];
}
int mid = (left + right) / 2;
int leftMode = findMode(a, left, mid);
int rightMode = findMode(a, mid + 1, right);
if (leftMode == rightMode) {
return leftMode;
} else {
int leftCount = 0, rightCount = 0;
for (int i = left; i <= right; i++) {
if (a[i] == leftMode) {
leftCount++;
} else if (a[i] == rightMode) {
rightCount++;
}
}
return leftCount > rightCount ? leftMode : rightMode;
}
}
```
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)