首页 > 试题广场 >

远亲不如近邻

[编程题]远亲不如近邻
  • 热度指数：6044 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
牛牛最近搬到了一座新的城镇，这个城镇可以看成是一个一维的坐标系。城镇上有n个居民，第i个居民的位置为a_i。现在牛牛有m个搬家方案，在第i个方案中他会搬到位置x_i。

俗话说的好，远亲不如近邻。现在牛牛想知道，对于每个搬家方案，搬家后与最近的居民的距离为多少。

示例1

输入

3,2,[2,4,7],[5,8]

输出

[1,1]

说明

第一个方案搬到位置5，与5最近的居民在位置4，距离为1.
第二个方案搬到位置8，与8最近的居民在位置7，距离为1

备注:
第一个参数为int型变量，代表居民个数n
第二个参数为int型变量，代表方案个数m
第三个参数为vector<int>，包含n个元素代表n个居民的位置
第四个参数为vector<int>，包含m个元素代表m个方案对应的位置

算法知识视频讲解
开通博客
头像 叫我第一名QAQ
发表于 2021-08-17 19:32:05
题目理解（Python） 首先，理解题目描述： 住户以横坐标形式的一维坐标系存在n，m，a，x分别代表：n，住户数量。m，方案个数。a，居民当前居住位置。x，方案中对应牛牛想要搬迁到的具***。则我们通过编程思维则可理解为n = len(a) 即当前所有住户的数量m = len(x) 即当前所有 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 未来0116
发表于 2021-08-08 22:16:35
一.题目描述NC533牛牛最近搬到了一座新的城镇，这个城镇可以看成是一个一维的坐标系。城镇上有n个居民，第i个居民的位置为ai。现在牛牛有m个搬家方案，在第i个方案中他会搬到位置xi。俗话说的好，远亲不如近邻。现在牛牛想知道，对于每个搬家方案，搬家后与最近的居民的距离为多少。二.算法(暴力模拟)理解 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 漫漫云天自翱翔
发表于 2021-08-13 22:22:18
题解一:暴力主要思路：①遍历方案数组，依次选取方案i②遍历居民位置，计算距离③对一个方案的所有距离求出最小距离，存入res数组 图示:复杂度分析:时间复杂度分析:，通过遍历每一个方案数，在与每一个居民计算距离，所以时间复杂度为;空间复杂度分析:，除返回结果数组外，没有申请其他额外空间 实现如下: c 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 积极的防守者
发表于 2020-02-13 21:07:35
普通解法 对于每个方案位置，暴力枚举所有居民位置。时间复杂度,空间复杂度. vector<int> solve(int n, int m, vector<int> a, vector<int> x){ vector<int> t(m); 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 球球了给孩子一个offer吧
发表于 2021-08-07 17:59:20
题目关键点：a数组元素是每个邻居在坐标上的位置（一维坐标），x数组元素是牛牛搬家之后在坐标上的位置要求每次搬家后最近邻居的最近距离 方法一：暴力解法枚举x数组和a数组，定义一个ans数组保存每轮循环中找到的x[i]与a[i]之差的最小绝对值 import java.util.*; public 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 摸鱼学大师
发表于 2021-08-05 14:02:43
思路： 题目的主要信息： a数组是每个邻居在坐标上的位置（一维坐标），x数组牛牛搬家之后在坐标上的位置 要求每次搬家后最近邻居的最近距离 方法一：暴力法具体做法：对于每一种搬家方案，遍历每个邻居的位置，直接算出距离维护最小值。 class Solution { public: vecto 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 认认真真coding
发表于 2021-08-03 16:59:31
题目描述牛牛最近搬到了一座新的城镇，这个城镇可以看成是一个一维的坐标系。城镇上有n个居民，第i个居民的位置为ai。现在牛牛有m个搬家方案，在第i个方案中他会搬到位置xi。 俗话说的好，远亲不如近邻。现在牛牛想知道，对于每个搬家方案，搬家后与最近的居民的距离为多少。 方法一：暴力解法 求解思路对于求解 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 不会做题的小菜鸡
发表于 2021-09-22 16:23:18
思路 题目分析 题目要求我们在一维城镇中选取一个轴上的位置居住，给出若干可选的居住点方案，计算每一个方案对应的距离居住居民的最小值。 其中n表示居民个数，m表示可选的方案数量，a表示具体的居民居住方案，x表示牛牛可选方案 一种方法就是我们枚举所有的居民居住的位置，分别与所有的可选方案进行一 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

二分 排序
难度：
10条回答 5716浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号