[编程题]相差不超过k的最多数
双指针滑动窗口。先对数列排序。给定一个滑动窗口，如果窗口右侧与左侧的元素差值不超过k，那么这个窗口内的任意两个元素插值不会超过k。这样子这个窗口长度就是我们能选的元素个数了。我们遍历这个数组，争取窗口长度最大化，用贪心的方法得到结果。
class MainActivity:
def main(self):
# Read the data
n, k = map(int, filter(lambda x: len(x) > 0, input().split(' ')))
nums = list(map(int, filter(lambda x: len(x) > 0, input().split(' '))))
# Initialization
nums.sort()
leftPtr = 0
rightPtr = 1
result = 0
# Traverse
if nums[-1] - nums[0] <= k:
print(n)
return
while rightPtr < n:
num = nums[rightPtr]
while num - nums[leftPtr] > k and leftPtr < rightPtr:
leftPtr += 1
result = max(result, rightPtr - leftPtr + 1)
rightPtr += 1
print(result)
if __name__ == '__main__':
M = MainActivity()
M.main()
发表于 2024-09-06 16:51:48
回复(0)
def func(n, k, alist): if n <= 0: return 0 res = 0 lp = 0 alist.sort() for rp in range(n): if lp < n and alist[rp] - alist[lp] > k: lp += 1 res = max(res, rp-lp+1) return res n, k = map(int, input().strip().split()) alist = list(map(int, input().strip().split())) print(func(n, k, alist))
发表于 2024-08-31 23:15:22
回复(0)
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int k = in.nextInt();
in.nextLine();
int nums[] = new int[n];
for(int i = 0;i < n;i++){
nums[i] = in.nextInt();
}
Arrays.sort(nums);
// 快慢指针定义
int slow = 0;
int fast = 0;
int res = 0;
while(fast < n){
if(nums[fast] - nums[slow] > k){
res = Math.max(res,fast - slow);
slow++;
continue;
}
fast++;
}
res = Math.max(res,fast - slow);
System.out.println(res);
}
}
编辑于 2024-02-23 15:37:49
回复(0)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n, k;
cin>>n>>k;
vector<int> arr(n);
for(int i=0; i<n; i++){
cin>>arr[i];
}
sort(arr.begin(),arr.end());
int l=0, r=1, max_value=0;
while(r<n){
if(arr[r]-arr[l]<=k){
max_value = max(max_value, r-l+1);
r++;
}else{
l++;
}
}
max_value = max(max_value,r-l);
cout<<max_value;
return 0;
}
发表于 2024-01-01 15:37:15
回复(0)
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2e5+10;
int a[N],n,k;
int main() {
cin>>n>>k;
for(int i = 0;i<n;i++)
cin>>a[i];
sort(a,a+n);
int l = 0,r =1,cnt = 1;
for(int i = l;i<n;i++)
{
while(r < n && a[r] - a[i] <= k)
{
if(cnt < r-i+1)
cnt = r-i+1;
r++;
}
}
cout << cnt;
return 0;
}
发表于 2023-11-22 00:09:31
回复(0)
滑动窗口
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)
离谱！！！ 一模一样的代码在vscode运行是对的，在牛客就不对
到底是哪里出了问题
const rl = require("readline").createInterface({ input: process.stdin });
let countLine = 0;
let n, k, nums;
rl.on("line", (line) => {
if (countLine === 0) {
n = line.split(" ").map(Number)[0];
k = line.split(" ").map(Number)[1];
} else if (countLine === 1) {
nums = line.split(" ").map(Number);
}
countLine++;
if (countLine === 2) {
nums.sort((a, b) => {
return a - b;
});
// console.log(nums);
let l = 0,
r = 0,
res = 0;
while (r < n) {
if(nums[r] - nums[l] > k){
l++;
}
res = Math.max(r - l + 1, res);
r++;
}
console.log(res);
rl.close();
}
});
发表于 2023-08-02 16:14:06
回复(0)
package main
import (
"fmt"
"os"
"bufio"
"sort"
)
var in=bufio.NewReader(os.Stdin)
func main() {
var n,k int
fmt.Scan(&n,&k)
arr:=make([]int,n)
for i:=0;i<n;i++{
fmt.Fscan(in,&arr[i])
}
sort.Ints(arr)
ans:=0
for l,r:=0,0;r<len(arr);r++{
for arr[r]-arr[l]>k{
l++
}
if r-l+1>ans{
ans=r-l+1
}
}
fmt.Print(ans)
}
发表于 2023-02-10 01:27:56
回复(0)
#include <iostream>
#include <algorithm>
int main()
{
int n, k;
std::cin >> n >> k;
int nums[n];
for(int i = 0; i < n; ++i)
std::cin >> nums[i];
std::sort(nums, nums + n);
int left = 0, right = 1;
int maxCnt = 0;
while(right < n)
{
if (nums[right] - nums[left] <= k)
maxCnt = std::max(maxCnt, right - left + 1);
else
++left;
++right;
}
std::cout << maxCnt;
}
发表于 2023-01-08 12:42:00
回复(0)
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int main() {
long long n,k;
cin>>n>>k;
long long a[n];
for(long long i=0;i<n;i++)
{cin>>a[i];
}
long long max=0;
sort(a,a+n);
for(long long j=0;j<n;j++)
{long long t;
for(long long i=n-1;i>j;i--)
{if(a[i]-a[j]<=k)
{t=i;break;}
else continue;}
if(t-j>max)
{
max=t-j+1;
}
}
cout<<max;
}
发表于 2022-11-08 23:08:25
回复(1)
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)
3 540400438
625059883 614901161 979280925
郁闷的要死，为什么这个用例自测运行时结果是对的，但保存并提交就报错不通过
const line1 = readline().split(" ");
const len = Number(line1[0]),
k = Number(line1[1]);
const line2 = readline()
.split(" ")
.map((item) => Number(item))
.sort((a,b)=>a - b)
let maxItems = 0;
console.log(line2)
for (let i = 0; i < len; i++) {
let start = i,end = len - 1
while ((line2[end] -line2[start]) > k) {
end -= 1
}
const items = end - start + 1;
if (maxItems < items) {
maxItems = items;
}
if (items === len) break;
//console.log(items)
}
print(maxItems);
const len = Number(line1[0]),
k = Number(line1[1]);
const line2 = readline()
.split(" ")
.map((item) => Number(item))
.sort((a,b)=>a - b)
let maxItems = 0;
console.log(line2)
for (let i = 0; i < len; i++) {
let start = i,end = len - 1
while ((line2[end] -line2[start]) > k) {
end -= 1
}
const items = end - start + 1;
if (maxItems < items) {
maxItems = items;
}
if (items === len) break;
//console.log(items)
}
print(maxItems);
发表于 2022-05-22 23:03:56
回复(0)
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);
}
}
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)
def func(n, arr, k): arr = sorted(arr) ans = 0 l = r = 0 while r < n: if arr[r] - arr[l] <= k: ans = max(ans, r - l + 1) else: l += 1 r += 1 return ans if __name__ == "__main__": n, k = [int(x) for x in input().split()] arr = [int(x) for x in input().split()] ans = func(n, arr, k) print(ans)
发表于 2022-03-28 09:41:19
回复(0)
问题信息
难度：
15条回答
48收藏
1461浏览
通过挑战的用户
查看代码-
2022-11-10 19:20:29
-
2022-11-03 22:42:40 -
2022-10-28 00:37:49
-
2022-10-15 19:11:04
-
2022-09-15 15:42:45
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
