给定一个数组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; }