原文：
给定两个整数k， x和一个arr[]，它们由n个不同的元素组成， 任务是从给定数组中找到最接近的x个元素。
示例：
输入：
arr[] = {1, 2, 3, 4, 10}, k = 3, x = 2输出：
2 3说明：给定数组中存在的第
k个最小元素是 3，最接近x = 2的数组元素是{2, 3}或{3, 4}。因此，所需的输出为
2 3。输入：
arr[] = {1, 9, 8, 2, 7, 3, 6, 4, 5, 10, 13, 12, 16, 14, 11, 15}, k = 3, x = 5输出：
1 2 3 4 5
朴素的方法：解决此问题的最简单方法是，并使用，打印最接近给定数组的第k个最小元素的x。
时间复杂度：o(n * log n)。
辅助空间：o(1)。
有效方法：为了优化上述方法，其思想是使用来有效计算给定数组的第k个最小元素的值 。 请按照以下步骤解决问题：
-
使用计算给定数组的第
k小，即kthelem。 -
初始化一个数组，例如说
diff[]，以存储arr[i]和kthelem的绝对差。 -
创建一个，例如说映射以将数组的每个元素映射到当前元素和
kthelem的绝对差。 -
遍历给定数组，并将
arr[i]附加到map[abs(kthelem – arr[i])]。 -
使用计算
diff[]数组的第x个最小元素，例如xthelem，来打印x个最接近的项目。 -
最后，遍历
diff[]数组，并检查xthelem是否小于或等于diff[i]。 如果确定为true，则在映射的帮助下打印数组的元素。
下面是上述方法的实现：
python3
# python3 program to implement
# the above approach
import collections
# function to swap
# two elements of array
def swap(arr, a, b):
temp = arr[a]
arr[a] = arr[b]
arr[b] = temp
# function to partition
# the array around x
def partition(arr, l, r, x):
# traverse array
# from index l to r
for i in range(l, r):
# partition array
# around x
if arr[i] == x:
swap(arr, r, i)
break
x = arr[r]
i = l
# traverse array
# from index l to r
for j in range(l, r):
if (arr[j] <= x):
swap(arr, i, j)
i = 1
swap(arr, i, r)
return i
# function to find
# median of arr[]
# from index l to l n
def findmedian(arr, l, n):
lis = []
for i in range(l, l n):
lis.append(arr[i])
# sort the array
lis.sort()
# return middle element
return lis[n // 2]
# function to get
# the kth smallest element
def kthsmallest(arr, l, r, k):
# if k is smaller than
# number of elements
# in array
if (k > 0 and
k <= r - l 1):
# stores count of
# elements in arr[l..r]
n = r - l 1
# divide arr[] in groups
# of size 5, calculate
# median of every group
# and store it in
# median[] array.
median = []
i = 0
while (i < n // 5):
median.append(
findmedian(arr,
l i * 5, 5))
i = 1
# for last group with
# less than 5 elements
if (i * 5 < n):
median.append(
findmedian(arr,
l i * 5, n % 5))
i = 1
# if median[] has
# only one element
if i == 1:
medofmed = median[i - 1]
# find median of all medians
# using recursive call.
else:
medofmed = kthsmallest(
median, 0, i - 1, i // 2)
# stores position of pivot
# element in sorted array
pos = partition(arr, l, r,
medofmed)
# if position is same as k
if (pos - l == k - 1):
return arr[pos]
# if position is more,
if (pos - l > k - 1):
# recur for left subarray
return kthsmallest(arr, l,
pos - 1, k)
# else recur for right subarray
return kthsmallest(arr, pos 1,
r, k - pos l - 1)
# if k is more than
# number of elements
# in the array
return 999999999999
# function to print
def closestelements(arr, k, x):
# stores size of arr
n = len(arr)
# stores kth smallest
# of the given array
kthelem = kthsmallest(
arr, 0, n - 1, k)
# store the value of
# abs(kthelem - arr[i])
diff = []
# create a map to map
# array element to
# abs(kthelem - arr[i])
maps = collections.defaultdict(
list)
for elem in arr:
# stres the value of
# abs(elem - kthelem)
temp = abs(elem - kthelem)
# map array elements
maps[temp].append(elem)
# append temp
diff.append(temp)
xthelem = kthsmallest(diff, 0,
n - 1, x)
# store x closest elements
res = set()
# traverse diff[] array
for dx in diff:
# if absolute difference is
# less than or eqaul to xthelem
if dx <= xthelem:
# append closest elements
for elem in maps[dx]:
if len(res) < x:
res.add(elem)
return res
# driver code
if __name__ == '__main__':
arr = [1, 2, 3, 4, 10, 15]
k = 3
x = 2
# store x closest elements
res = closestelements(arr, k, x)
# print x closest elements
for i in res:
print(i, end =" ");
输出：
2 3
时间复杂度：o(n)。
辅助空间：o(n)。
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
