使用c语言,编写寻找多数元素程序
时间: 2024-09-24 14:30:45 浏览: 42
在C语言中,编写一个寻找数组中多数元素的程序可以使用哈希表(如桶排序或计数排序的思想)或者简单遍历两次数组的方法。这里我们给出一种常见的解决方案,即使用两趟遍历来找到最大值和最小值,同时计算每个元素出现的次数。如果这两个值相等,那么它们就是多数元素。
以下是简单的实现:
```c
#include <stdio.h>
int majorityElement(int arr[], int n) {
if (n == 0) return -1; // 如果数组为空,返回-1
int count[1000] = {0}; // 初始化一个计数数组,假设元素范围是0到999
int candidate1 = arr[0], candidate2 = arr[0]; // 两个候选多数元素
for (int i = 0; i < n; i++) {
count[arr[i]]++; // 对每个元素计数
// 如果当前计数超过了数组一半,更新候选多数元素
if (count[arr[i]] > n / 2) {
if (candidate2 == arr[i])
candidate2 = arr[i];
else
candidate1 = arr[i];
}
}
// 再次遍历数组,统计候选元素出现的次数
int cnt1 = 0, cnt2 = 0;
for (int i = 0; i < n; i++) {
if (arr[i] == candidate1)
cnt1++;
else if (arr[i] == candidate2)
cnt2++;
}
// 如果cnt1或cnt2大于等于n/2,则候选元素即为多数元素
if (cnt1 >= n / 2 || cnt2 >= n / 2)
return candidate1;
return -1; // 如果找不到满足条件的多数元素,返回-1
}
int main() {
int arr[] = {2, 2, 1, 1, 1, 2, 2};
int n = sizeof(arr) / sizeof(arr[0]);
int result = majorityElement(arr, n);
printf("Majority element is: %d\n", result);
return 0;
}
阅读全文