阿里云笔试阿里云笔试题 0414

笔试时间：2024年04月14日

历史笔试传送门：2023秋招笔试合集

第一题

题目

给你一个长度为n的数组a，可以对数组一个元素进行减半，问操作后数组众数的最大值。

输入描述

第一行输入一个正整数n，代表数组长度，第二行 n 个整数，表示输入的数组 a

输出描述

一个整数 x，表示操作后数组众数的最大值。

样例输入

5

1 3 2 2 5

样例输出

2

参考题解

枚举每个数X，如果数2X 或2X+1 存在，那么当前数的出现次数可以增加1。如果大于n/2，更新答案。

C++：[此代码未进行大量数据的测试，仅供参考]

#include <bits/stdc++.h>

const int inf = 0x3f3f3f3f;
using i64 = long long;

void solve() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    std::map<int, int> cnt;
    
    for (int i = 0; i < n; ++i) {
     std::cin >> a[i];
     cnt[a[i]]++;
    }
 
    int ans = 0;
    if (n == 1) {
     std::cout << a[0] / 2 << "\n";
     return;
    }

    for (int i = 0; i < n; ++i) {
     if (cnt.count(a[i] * 2) or cnt.count(a[i] * 2 + 1)) {
      if ((cnt[a[i]] + 1) * 2 >= n) {
       ans = std::max(ans, a[i]);
      }
     }
     if (cnt[a[i]] * 2 >= n) {
      ans = std::max(ans, a[i]);
     }
    }
    std::cout << ans << "\n";
}

int main() {
    std::cin.sync_with_stdio(false);
    std::cin.tie(0);
    
    solve();

    return 0;
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        solve(sc);
    }

    static void solve(Scanner sc) {
        int n = sc.nextInt();
        int[] a = new int[n];
        Map<Integer, Integer> cnt = new HashMap<>();

        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
            cnt.put(a[i], cnt.getOrDefault(a[i], 0) + 1);
        }

        int ans = 0;
        if (n == 1) {
            System.out.println(a[0] / 2);
            return;
        }

        for (int i = 0; i < n; i++) {
            if (cnt.containsKey(a[i] * 2) || cnt.containsKey(a[i] * 2 + 1)) {
                if ((cnt.get(a[i]) + 1) * 2 >= n) {
                    ans = Math.max(ans, a[i]);
                }
            }
            if (cnt.get(a[i]) * 2 >= n) {
                ans = Math.max(ans, a[i]);
            }
        }
        System.out.println(ans);
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

def solve():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    n = int(data[0])
    a = list(map(int, data[1:n+1]))
    cnt = {}
    
    for num in a:
        if num in cnt:
            cnt[num] += 1
        else:
            cnt[num] = 1
    
    ans = 0
    if n == 1:
        print(a[0] // 2)
        return
    
    for num in a:
        if (num * 2 in cnt) or (num * 2 + 1 in cnt):
            if (cnt[num] + 1) * 2 >= n:
                ans = max(ans, num)
        if cnt[num] * 2 >= n:
            ans = max(ans, num)
    
    print(ans)

if __name__ == "__main__":
    import sys
    input = sys.stdin.read
    solve()