from collections import defaultdict
n = int(input())
nums = list(map(int,input().split()))
k = int(input())
cont = defaultdict(int)
min_mod = {}
for x in nums:
    rest = x%k
    cont[rest]+=1
    if rest not in min_mod:
        min_mod[rest]=x
    else:
        min_mod[rest]=min(min_mod[rest],x)

res = 0
min_value = -1
for rest,x in min_mod.items():
    lenth = cont[rest]
    if lenth>res:
        res = lenth
        min_value = x
    elif lenth==res and x<min_value:
        min_value = x
print(min_value)

哈希表仅记录同余数组最小元素和数组大小，O(n)复杂度实现同余哈希表，再通过二元数组(-同余次数，最小起点)排序，即可得到解。

#include <bits/stdc++.h>
using namespace std;


int main()
{
    int n, inter;
    cin>>n;
    vector<int> input(n);
    unordered_map<int, pair<int, int>> mp;
    for (int i=0; i<n; i++) {
        // int x;
        cin>>input[i];
    }
    cin>>inter;
    // cout<<n<<endl;
    for (int i=0; i<n; i++) {
        // int x;
        int idx=input[i]%inter;
        if (mp.find(idx)==mp.end()) {
            mp[idx].first=input[i];
            mp[idx].second++;
        } else {
            mp[idx].first=min(input[i], mp[idx].first);
            mp[idx].second++;
        }

    }

    vector<vector<int>> ans(mp.size(), vector<int>(2,0));
    int i=0;
    for (auto item: mp) {
        auto s=item.second;
        ans[i][0]=-s.second;
        ans[i][1]=s.first;
        i++;
    }
    sort(ans.begin(),ans.end());

    cout<<ans[0][1]<<endl;
    return 0;
}

题意化简

给定一个数组，求选择出一个 最长的 公差为 $k$ 的等差数列。如果有多个这样的等差数列，选择起点最小的那个。

思路:哈希表 + 枚举 + 同余

1.如何判断两个数是否处在同一个间隔为k的等差数列中？

他们同时对k取模，得到这个序列的最小非负整数，如果相等，则处于同一个等差序列。这样我们只需要用哈希表统计a[i] % k的个数。

解释

k = 3 , 初始值 s = 10

arr = [10 , 13 , 16 , 19 , 22 , ...]

对于序列里的10 , 13 , 22 , 他们 % k 都等于 1

这是因为，他们都能写成$1 + a * k$ 的形式。而不管a取多少.后面的a * k 都会被取模为0.

2.多个可能的答案

序列中可能有多个包含最多元素的等差数列，我们只需要使用一个哈希表记录x % k 的最小可能即可。

坑点：据提前交卷的考生反应，java，python时限只有200ms，考场上正确做法貌似只能过40%，其他超时

代码

python

from collections import defaultdict
# 读入数组长度和间隔
n = int(input())
a = list(map(int, input().split()))
k = int(input())
# mod统计余数为x的元素的实际最小值
mod = {}
# book[x]统计 属于首项为x的等差数列 的元素个数
book = defaultdict(int)
for x in a:
    rest = x % k
    book[rest] += 1
    if rest not in mod:
        mod[rest] = x
    else:
        # 保留最小的值
        mod[rest] = min(x, mod[rest])

res = 0
mim_val = -1
for rest, value in mod.items():
    x = book[rest]
    # 保留出现次数最多的等差数列
    if x > res:
        res = x
        mim_val = value
    # 出现次数相同，保留最小的值
    elif x == res and value < mim_val:
        mim_val = value
# 输出
print(mim_val)

Java

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        
        // 读取输入的整数个数n
        int n = in.nextInt();
        int[] nums = new int[n]; // 创建数组存储输入的整数
        
        // 读取n个整数
        for(int i = 0; i < n; i++) {
            nums[i] = in.nextInt();
        }
        
        // 读取间隔k
        int k = in.nextInt();
        
        // 创建两个哈希表，一个用于统计模k的频率，另一个用于记录最小整数
        Map<Integer, Integer> map = new HashMap<>();
        Map<Integer, Integer> rec = new HashMap<>();
        
        int max = 0; // 用于记录当前最大频率
        int ans = Integer.MAX_VALUE; // 用于记录答案，初始化为最大值
        
        // 遍历输入的整数数组
        for(int i = 0; i < n; i++) {
            int tmp = nums[i] % k; // 计算当前数与k的同余
            
            // 更新模k的频率
            map.put(tmp, map.getOrDefault(tmp, 0) + 1);
            
            // 记录当前模k值对应的最小整数
            if(!rec.containsKey(tmp) || rec.get(tmp) > nums[i]) {
                rec.put(tmp, nums[i]);
            }
        }
        
        // 遍历频率表，查找出现频率最高的模k值
        for(Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if(entry.getValue() >= max) {
                // 如果频率相同，选择最小的整数
                if(entry.getValue() == max) {
                    ans = Math.min(ans, rec.get(entry.getKey()));
                } else {
                    ans = rec.get(entry.getKey()); // 更新答案
                }
                
                max = entry.getValue(); // 更新最大频率
            }
        }
        
        // 输出结果，即满足条件的最小整数
        System.out.println(ans);
    }
}

C++

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <climits>
#include <unordered_set>
using namespace std;

int main() {
    int n; // 输入整数的个数
    cin >> n;
    vector<long long int> nums(n, 0); // 创建一个长整型数组用于存储输入的整数
    long long int c; // 用于临时存储输入的整数
    
    // 读取n个整数并存入nums数组
    for(int i = 0; i < n; i++) {
        cin >> c;
        nums[i] = c; // 将输入的整数赋值到数组中
    }
    
    int interval; // 输入的间隔
    cin >> interval;
    
    long long int res = LLONG_MAX; // 初始化结果为最大长整型值
    int del = 0; // 用于记录出现频率最高的模值的个数
    
    // 创建一个映射，用于存储每个模值及其对应的数值列表
    map<long long int, vector<long long int>> mp_1;
    for(int i = 0; i < n; i++) {
        // 将每个数值按模interval分组
        mp_1[nums[i] % interval].push_back(nums[i]);
    }
    
    // 遍历映射，找出出现频率最高的模值
    for(auto& m : mp_1) {
        // 如果当前模值的数量超过已记录的最大数量
        if(del < (int)m.second.size()) {
            del = (int)m.second.size(); // 更新最大数量
            sort(m.second.begin(), m.second.end()); // 对当前模值的数值列表进行排序
            res = m.second[0]; // 记录当前模值的最小数
        } else if(del == (int)m.second.size()) {
            // 如果当前模值的数量与已记录的最大数量相同，更新结果
            for(int i = 0; i < (int)m.second.size(); i++) {
                res = min(res, m.second[i]); // 取当前最小值
            }
        }
    }

    // 输出结果，即满足条件的最小整数
    cout << res;
    return 0; // 结束程序
}

OJ会员可以通过点击题目上方《已通过》查看其他通过代码来学习。