深高北-第11课

张kk

2024-12-12 16:08:24

发布于：广东

61阅读

0回复

0点赞

桶标记思想：
①定义桶数组，长度为数据的最大范围，注意！是数据的最大范围，而不是数量n，桶的下标可以作为数字；比如数据范围是0-10000,n个数据，n的范围是0-100

int tong[10010];

②桶标记（插旗的过程）：每次输入一个数据，就往这个数据对应的桶编号+1

cin>>k;
tong[k]++;

③遍历桶；注意：范围是到桶数组的最大下标-1

for(int i=1;i<10010;i++){
    tong[i];
}

例题：
A367.超过一半的数

题目描述
给你n个数,找出出现次数超过一半的数,保证存在这样一个数

输入格式
第一行输入一个整数n , (n<=1000）
第二行输入n个整数(<1000000)

#include <iostream>
#include <cmath>
using namespace std;
//定义桶
int tong[1000010];
int main(){
    int n,a;
    cin>>n;
    //输入n个数据
    for(int i=1;i<=n;i++){
        cin>>a;
        //插旗
        tong[a]++;
    }
    //遍历桶
    for(int i=1;i<1000010;i++){
        if(tong[i]>n/2){
            cout<<i;
        }
    }
    return 0;
}

有帮助，赞一个

去预览

0/2000

这里空空如也

热门讨论