相差不超过k的最多数

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

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

给定一个数组，选择一些数，要求选择的数中任意两数差的绝对值不超过 $k$ 。问最多能选择多少个数？

输入描述:

第一行输入两个正整数 和。
第二行输入  个正整数，用空格隔开，表示这个数组。

输出描述:

一个正整数，代表能选的最多数量。
数据范围：

示例1

输入

5 3
2 1 5 3 2

输出

说明

显然，1和5不能同时选。所以最多只能选4个数。

算法知识视频讲解

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)