首页 > 试题广场 >

查找数组众数

[编程题]查找数组众数
  • 热度指数:5445 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解

给定一个数组A[n], 定义数组的众数 ( Majority Element) 为数组中出现次数超过 n/2 次的元素, 假设数组A[n]非空且一定存在众数, 请设计算法找到该众数并输出.


输入描述:
一个非空且一定存在众数的整数数组,如: [1,2,2]


输出描述:
输出打印该众数,如: 2
示例1

输入

[1,2,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;
}

发表于 2024-07-13 23:47:48 回复(0)