给定一个数组A[n], 定义数组的众数 ( Majority Element) 为数组中出现次数超过 n/2 次的元素, 假设数组A[n]非空且一定存在众数, 请设计算法找到该众数并输出.
给定一个数组A[n], 定义数组的众数 ( Majority Element) 为数组中出现次数超过 n/2 次的元素, 假设数组A[n]非空且一定存在众数, 请设计算法找到该众数并输出.
一个非空且一定存在众数的整数数组,如: [1,2,2]
输出打印该众数,如: 2
[1,2,2]
2
[3,1,-2,3,1,3,3]
3
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 1000
#define MAX_VAL 2000
int main() {
int arr[MAX_SIZE] = {0};
int i = 0;
char input[MAX_SIZE];
int num;
//录入数组
fgets(input, sizeof(input), stdin);
char *ptr = input + 1;
while (*ptr != ']' && *ptr != '\0') {
if (isdigit(*ptr) || *ptr == '-' || *ptr == '+') {
sscanf(ptr, "%d", &num);
arr[i++] = num;
}
while (isdigit(*ptr) || *ptr == '-' || *ptr == '+') ptr++;
if (*ptr == ',') ptr++;
}
//寻找出现最多的数(哈希数组思路)
int count[MAX_VAL] = {0};
int max_count = 0;
for (int j = 0; j < i; j++) {
count[arr[j] + 1000]++;
}
for (int m = 0; m < MAX_VAL; m++) {
if (count[m] > i / 2) printf("%d", m - 1000);
}
return 0;
}