首页 > 试题广场 >

最接近的K个元素

[编程题]最接近的K个元素

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

给定一个长度为 n 的升序数组 nums 和两个整数 k 和 x ，从数组中找到最接近 x (两数之差最小)的 k 个数并升序得输出他们。

整数 a 比整数 b 更接近 x 需要满足

|a-x| < |b-x| ，

|a-x| = |b-x| 时 a < b

数据范围： $1 \le k \le n \le 10^5 \$ ， $|nums_i| ,| x| \le 10^4 \$

示例1

输入

[1,2,3,4,5],4,4

输出

[2,3,4,5]

示例2

输入

[1,2,3,4,5],4,3

输出

[1,2,3,4]

示例3

输入

[1,2,3,4],4,0

输出

[1,2,3,4]

算法知识视频讲解

碧秋

构造一个结构体，利用辅助数组记录差值

struct node{
	int val;//绝对值
	int index;//对应原数组中的下标
};
int cmp1(const void* a,const void* b){
	struct node* x=(struct node*)a;
	struct node* y=(struct node*)b;
	return x->val-y->val;
}
int cmp2(const void* a,const void* b){
	struct node* x=(struct node*)a;
	struct node* y=(struct node*)b;
	return x->index-y->index;
}
int* closestElement(int* nums, int numsLen, int k, int x, int* returnSize ) {
	*returnSize=k;
	int* res=(int*)malloc(sizeof(int)*k);
    struct node* arr=(struct node*)malloc(sizeof(struct node)*numsLen);
	for(int i=0;i<numsLen;i++){
		arr[i].val=abs(nums[i]-x);//辅助数组记录差值的绝对值
		arr[i].index=i;//记录下标
	}
	qsort(arr,numsLen,sizeof(struct node),cmp1);//先比较差值
	qsort(arr,k,sizeof(struct node),cmp2);//再比较下标，排序
	for(int j=0;j<k;j++){
		res[j]=nums[arr[j].index];
	}
	return res;
}

发表于 2023-03-16 19:55:09 回复(0)

Java

xinychan

import java.util.*;

public class Solution {

// 所有数据先减x；再取绝对值；得到与x之差的数组，且均为正整数

// 在x之差的数组中，找到数值最小的数；记录下标

// 最小值下标为中心，双指针法移动，获取k个数；保存这k个数的下标

// 对下标进行排序，然后按照下标到 nums 取出数据

public ArrayList<Integer> closestElement(ArrayList<Integer> nums, int k, int x) {

// 所有数据先减x；再取绝对值；得到与x之差的数组，且均为正整数

ArrayList<Integer> absList = new ArrayList<>();

for (int val : nums) {

absList.add(Math.abs(val - x));

}

// 在x之差的数组中，找到数值最小的数；记录下标

int minNum = Integer.MAX_VALUE;

int minIndex = -1;

int absSize = absList.size();

for (int i = 0; i < absSize; i++) {

int val = absList.get(i);

if (val < minNum) {

minNum = val;

minIndex = i;

}

// 最小值下标为中心，双指针法移动，获取k个数；保存这k个数的下标

ArrayList<Integer> idxList = new ArrayList<>();

// 题目 k>=1；至少要保存一个最小值

idxList.add(minIndex);

int times = 0;

int left = minIndex - 1;

int right = minIndex + 1;

// 已经保存过了 minIndex，保存的下标需要减1

while (times < k - 1) {

if (left < 0) {

// left 下标小于0时，移动 right 下标

idxList.add(right);

right++;

} else if (right >= absSize) {

// right 下标小于列表长度，移动 left 下标

idxList.add(left);

left--;

} else {

// left/right 在列表长度之内，计算与X之差的大小；那个小就保存下标

if (absList.get(left) <= absList.get(right)) {

idxList.add(left);

left--;

} else {

idxList.add(right);

right++;

}

times++;

}

// 对下标列表排序，获取升序后的下标

Collections.sort(idxList);

// 依据下标获取 nums 源数据

ArrayList<Integer> result = new ArrayList<>();

for (int i = 0; i < idxList.size(); i++) {

int index = idxList.get(i);

int val = nums.get(index);

result.add(val);

}

return result;

}

发表于 2022-12-13 01:04:07 回复(0)

牛客774217147号

def closestElement(self , nums: List[int], k: int, x: int) -> List[int]:

min_diff = 1e-31

is_minst = False

idx = 0

# for idx,tmp in enumerate(nums):

# diff = abs(tmp-x)

# if abs(tmp-x)<min_diff:

# min_diff = abs(tmp-x)

# elif abs(tmp-x)>min_diff:

# is_minst = True

# break

diff = [abs(tmp-x) for tmp in nums]

diff.sort()

idx = nums.index(x + diff[0])

if idx==-1:

idx = nums.index(x - diff[0])

min_loc = idx

# min_loc = idx - 1

rslt = [nums[min_loc]]

print(rslt)

offset_l = -1

offset_r = 1

while len(rslt) < k:

print("l:",offset_l,";;r:",offset_r)

if abs(nums[min_loc + offset_l] - x) <= abs(nums[min_loc + offset_r] - x):

rslt.append(nums[min_loc + offset_l])

offset_l = offset_l-1

# # elif abs(nums[min_loc + offset_l] - x) == abs(nums[min_loc + offset_r] - x):

# # rslt.append(nums[min_loc + offset_l])

# offset_l = offset_l-1

else:

rslt.append(nums[min_loc + offset_r])

offset_r = offset_r + 1

rslt.sort()

return rslt

发表于 2022-12-01 21:39:27 回复(0)

skwan

import java.util.*;


public class Solution {
    /**
        双指针
    **/
    public ArrayList<Integer> closestElement (ArrayList<Integer> nums, int k, int x) {
        int n = nums.size(), left = 0, right = n - 1;
        while (right >= left + k) {
            if (Math.abs(nums.get(right) - x) >= Math.abs(nums.get(left) - x)) {
                right--;
            } else {
                left++;
            }
        }
        ArrayList<Integer> ans = new ArrayList<>(k);
        for (int i = left; i < left + k; i++) {
            ans.add(nums.get(i));
        }
        return ans;
    }
}

发表于 2022-07-17 20:45:17 回复(0)

Python2

菜鸡升职记

# -*- coding: utf-8 -*-

import bisect


#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param nums int整型一维数组
# @param k int整型
# @param x int整型
# @return int整型一维数组
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/b4d7edc45759453e9bc8ab71f0888e0f?tpId=196&tqId=40554&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3FjudgeStatus%3D3%26page%3D1%26pageSize%3D50%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=3&tags=&title=
    算法：
        1. 在升序数组nums中，二分查找大于等于x的下标right，与小于等于x的下标left
        2. 以区间[left, right]为中心，向外扩展，记录满足条件的元素：
            |a-x| < |b-x|
            |a-x| = |b-x| 时 a < b
    复杂度：
        时间复杂度：O(logn + k)
        空间复杂度：O(1)
    """

    def closestElement(self, nums, k, x):
        # write code here
        left = bisect.bisect_left(nums, x)

        if left > 0 and abs(nums[left - 1] - x) <= abs(nums[left] - x): # bisect.bisect_left返回的是nums中大于等于x的最小下标，所以这里最接近x的有可能是nums[left], 也可能是nums[left - 1]
            i, j = left - 1, left
        else:
            i, j = left, left + 1

        n, res = len(nums), []
        while i >= 0 and j < n and k > 0:
            if abs(nums[i] - x) <= abs(nums[j] - x):
                res.insert(0, nums[i])
                i -= 1
            else:
                res.append(nums[j])
                j += 1
            k -= 1

        if i >= 0 and k > 0:
            res = nums[i - k + 1:i + 1] + res

        if j < n and k > 0:
            res += nums[j: j + k]

        return res


if __name__ == "__main__":
    sol = Solution()

    nums, k, x = [1, 2, 3, 4, 5], 4, 4

    # nums, k, x = [1, 2, 3, 4, 5], 4, 3

    # nums, k, x = [1, 2, 3, 4], 4, 0

    # nums, k, x = [1, 3, 8, 9], 1, 5

    res = sol.closestElement(nums, k, x)

    print res

发表于 2022-07-07 17:04:13 回复(0)