题意化简

给定一个数组，求选择出一个 最长的 公差为 $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会员可以通过点击题目上方《已通过》查看其他通过代码来学习。

题目内容

给定一个整数数组$nums$，同时给定一个整数$interval$。

指定数组$nums$中的某个元素作为起点，然后以$interval$ 为间隔递增，如果递增的数（包含起点）等于$nums$中的元素，则数组$nums$中对应的元素消除，返回消除元素最多的起点元素。如果消除的元素同样多，则返回最小的起点元素。

输入描述

输入格式：

第一行输入整数数组的长度$n$

第二行输入长度为$n$的整数数组$nums$

第三行输入整数$interval$

$1＜=n＜=10^5$

$0＜=nums[i]＜=10^8$

$0＜=interval＜=10^5$

输出描述

起点元素的最小值

样例1

输入

6
4 5 7 1 1 2
3

输出

1

说明

输入给定的间隔为$3$，如果以元素$1$为起点，则可以消除$1,4,7,10,...$这些元素，因此，我们可以消除给定数组中的$4,7,1,1$这$4$个元素，以其他元素为起点也没有办法消除更多元素了，因此返回$1$

样例2

输入

5
4 5 7 1 2
50

输出

1

说明

输入给定的间隔为$50$,如果以元素$1$为起点，则可以消除$1,51,101$这些元素，因此，我们可以消除给定数组中的$1$这个元素，同理，如果以$2$为起点，则可以消除$2,52,102$这些元素，因此我们可以消除给定数组中的$2$这个元素，以此类推，无论以哪个元素作为起点，都只能消除$1$个元素，因此返回最小的起点元素$1$。