拉票

[题目链接](https://www.nowcoder.com/practice/f1a2cd7a704443d08221d896d6d7a7c0)

思路

贪心。小明的基础票数是自己阵营 $x$ 中的人数。他可以额外游说一个阵营，为了票数最大化，显然应该选人数最多的非 $x$ 阵营。

做法：统计每个阵营的人数，答案 = 阵营 $x$ 的人数 + 其余阵营中人数最多的那个。若所有人都属于阵营 $x$ ，则不需要游说，答案就是 $n$ 。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。

代码

C++
Java

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n, x;
    scanf("%d%d", &n, &x);
    unordered_map<int,int> cnt;
    for(int i=0;i<n;i++){
        int a; scanf("%d",&a);
        cnt[a]++;
    }
    int base = cnt.count(x) ? cnt[x] : 0;
    int mx = 0;
    for(auto &[k,v]: cnt){
        if(k != x) mx = max(mx, v);
    }
    printf("%d\n", base + mx);
    return 0;
}

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), x = sc.nextInt();
        HashMap<Integer,Integer> cnt = new HashMap<>();
        for(int i=0;i<n;i++){
            int a = sc.nextInt();
            cnt.merge(a, 1, Integer::sum);
        }
        int base = cnt.getOrDefault(x, 0);
        int mx = 0;
        for(Map.Entry<Integer,Integer> e : cnt.entrySet()){
            if(e.getKey() != x) mx = Math.max(mx, e.getValue());
        }
        System.out.println(base + mx);
    }
}