首页 > 试题广场 >

相差不超过k的最多数

[编程题]相差不超过k的最多数

热度指数：10727 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\hspace{15pt}$ 给定一个包含 $n$ 个正整数的数组 $a_1,a_2,\dots ,a_n$ 。你需要从中选择若干个数（可以全部也可以一个都不选），使得在所选集合中任意两数的差的绝对值均不超过给定整数 $k$ 。
$\hspace{15pt}$ 请输出能够选出的元素个数的最大值。

【名词解释】
$\hspace{15pt}$ 若选出的元素集合为 $S$ ，则要求 $\max(S)-\min(S)\leqq k$ 。

输入描述:

第一行输入两个整数 。 
第二行输入  个整数 。

输出描述:

输出一个整数，表示满足条件的最多可选元素数量。

示例1

输入

5 3
2 1 5 3 2

输出

说明

选取元素集合  满足最大值与最小值之差为 ，且无法再加入 。

算法知识视频讲解

Java

六路折梅手

import java.util.*;
import java.io.*;
//随机选择数组元素可不按顺序
//数组先排序，排序后根据k获取区间长度
//因为最长区间可能是中间区间，所以还要全部遍历。
//排序后滑动找最大满足条件的滑动窗口
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
        String[] line1=bf.readLine().split(" ");
        int n=Integer.parseInt(line1[0]);
        int k=Integer.parseInt(line1[1]);
        int[] ch=Arrays.stream(bf.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        Arrays.sort(ch);
        int temp=0;//当前窗口
        int maxLen=0;//最大窗口

        //逐步滑动右侧，左侧按条件滑动
        for(int l=0, i=1;i<ch.length;i++){
            if(ch[i]-ch[l]<=k){
                temp++;//满足条件后统计长度并右侧滑动
                if(maxLen<temp){
                    maxLen=temp;
                }
            }else{
                //不满足条件时左侧滑动，同步右侧滑动r++。
                //此时窗口始终和上一次满足条件时窗口长度一致
                l++;
            }
        }

        System.out.println(maxLen+1);//没有输出为0的用例

        // if(maxLen!=0){
        //     System.out.println(maxLen+1);
        // }else{
        //     System.out.println(maxLen);
        // }

    }
}

发表于 2025-08-29 12:50:24 回复(0)

Java

wuxin368

滑动窗口

public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }
        Arrays.sort(arr);
        int a = 0, b = 0;
        int res = 1;
        while (b < n) {
            while (b < n && arr[b] - arr[a] <= k) b++;
            res = Math.max(res, b - a);
            if(b == n) break;
            while (a<b && arr[b] - arr[a] > k) a++;
        }
        System.out.println(res);
    }

发表于 2023-09-03 21:52:42 回复(0)

Java

牛客338107602号

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc= new Scanner(System.in);
        int n = sc.nextInt();//输入整数个数
        int k = sc.nextInt();//间隔k
        ArrayList<Integer> list = new ArrayList<>();
        for(int i=1;i<=n;i++){
            list.add(sc.nextInt());
        }
        Collections.sort(list);//将输入的整数从小到大排序
        int max = 0;
        int len = list.size();
        int start,end;
        for(start=0,end=0;end<len;){
            if(list.get(end)-list.get(start)<=k)
                end++;
            else{
                max = max<end-start?end-start:max;
                start++;
            }

        }
        max = max<end-start?end-start:max;
        System.out.println(max);
    }
}

发表于 2022-07-08 11:34:57 回复(0)

Java

牛客108255912号

import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
int num[] = new int[n];
for(int i = 0; i < n; i++){
num[i] = sc.nextInt();
}
Arrays.sort(num);
int left = 0;
int max = 0;
int sub = 0;
for(int i = 0; i < n; i++){
sub = num[i] - num[left];
while(sub > k){
left++;
sub = num[i] - num[left];
}
max = Math.max(max, i - left + 1);
}
System.out.println(max);
}
}

发表于 2022-04-06 21:17:35 回复(0)