J - Smallest Difference

J - Smallest Difference

You are given an array a consists of n elements, find the maximum number of elements you can select from the array such that the absolute difference between any two of the chosen elements is ?≤?1.

Input
The first line contains an integer T (1?≤?T?≤?100), in which T is the number of test cases.

The first line of each test case consist of an integer n (2?≤?n?≤?104), in which n is size of the array a

The a line follow containing n elements a1,?a2,?…,?an (1?≤?ai?≤?104), giving the array a.

Output
For each test case, print a single line containing the maximum number of elements you can select from the array such that the absolute difference between any two of the chosen elements is ?≤?1.

Example
Input
2
3
1 2 3
5
2 2 3 4 5
Output
2
3
大体意思就是给定一个数组，将其中的n个数列从中取出构成一个新的数列，要求新数列的任意两项之间的绝对值的差小于1
方法一

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    int t;int a[10010];scanf("%d",&t);int N=0;//记录输入的最大的数值while(t--){
    int n;scanf("%d",&n);memset(a,0,sizeof(a));//清空数组afor(int i=0;i<n;i++){
    int b;scanf("%d",&b);a[b]++;//记录数组元素中值为b的个数if(b>N)N=b;//记录数组元素中最大的数值}int maxx=0;//记录最大的相邻元素的总数for(int i=0;i<=N;i++){
    if(a[i]!=0)a[i]+=a[i+1];//并不使用a[i-1]是因为最小的数没有maxx=max(maxx,a[i]);}printf("%d\n",maxx);}
}

方法二

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
using namespace std;
int main()
{
    int t,a[10010];scanf("%d",&t);while(t--){
    memset(a,0,sizeof(a));int n,maxx=0;scanf("%d",&n);for(int i=0;i<n;i++)scanf("%d",&a[i]);sort(a,a+n);for(int i=0;i<n;i++){
    int num=0;for(int j=i;j>=0;j--){
    if(a[i]-a[j]<=1)num++;else break;}maxx=max(maxx,num);}printf("%d\n",maxx);}
}

此方法是直接计算有多少数字满足条件。
方法三

#include<bits/stdc++.h>
using namespace std;
int a[10050];
int main()
{
    int t;scanf("%d",&t);while(t--){
    int n;scanf("%d",&n);for(int i = 0; i < n; i ++) scanf("%d",&a[i]);sort(a,a + n);int l = 0,r = 0;int maxx = -1;for(int r = 0; r < n; r ++){
    while(a[r] - a[l] > 1)l ++;maxx = max(maxx,r - l + 1);}printf("%d\n",maxx);}return 0;
}

方法和2类似，是记录数组元素位置，并非直接历遍每一个元素