首页 > 试题广场 >

相差不超过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

输出

说明

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

算法知识视频讲解

Python3

想吃火锅的加菲猫是单身

1.排序

2.用一层指针从左到右遍历窗口值在[a[i],a[i]+k]范围内有多少个数，然后更新窗口大小

用二分查找来寻找最后一个小于或等于a[i]+k的下标，所以时间复杂度是O(nlogn)

def binary_search(a,l,r,target):
    # 返回最后一个比taregt小的坐标
    while l<r:
        mid = int((l+r) / 2)
        if a[mid] <= target:
            if mid+1>r:
                return mid
            elif a[mid+1]>target:
                return mid
            else:
                l = mid+1
        else:
            r = mid-1
    return l
n, k = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
res  = 0
for i in range(n):
    l = i
    r = binary_search(a,l+1,n-1,a[i]+k)
    res = max(res,r-l+1)
print(res)

发表于 2025-01-31 11:33:30 回复(0)

Python3

牛客804244365号

n,k = map(int,input().split())

l = list(map(int,input().split()))

l.sort()

i , j =0 , 0

while j < n:

if l[j]-l[i] <= k:

j += 1

else:

i += 1

j += 1

print(j-i)

窗口长度即为最大长度

发表于 2024-12-18 17:45:18 回复(0)

Python3

TS9527

双指针滑动窗口。先对数列排序。给定一个滑动窗口，如果窗口右侧与左侧的元素差值不超过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)

Python3

Cecilia_mm

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)