首页 > 试题广场 >

远亲不如近邻

[编程题]远亲不如近邻

热度指数：6049 时间限制：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个方案对应的位置

算法知识视频讲解

广州市民林先生

class Solution {
public:
    vector<int> solve(int n, int m, vector<int>& a, vector<int>& x) {
        // m -> x[]
        // n -> a[]
        // 在x里找一个数x[i]，再在a里找一个数a[i]，使得a[i]和x[i]距离最小，计算出距离
        vector<int> res;
        sort(a.begin(), a.end());
        for(int i = 1; i <= m; ++i){
            //每个方案
            int temp = x[i - 1];
            //二分
            int m1 = 0;
            int n1 = a.size() - 1;
            int drop = INT_MAX;
            while(m1 <= n1){
                int mid = m1 + (n1 - m1)/2;
                if(abs(a[mid] - temp) < drop){
                    drop = abs(a[mid] - temp);
                }
                if(a[mid] < temp){
                    m1 = mid + 1;
                }
                else if(a[mid] > temp){
                    n1 = mid - 1;
                }
                else{
                    drop = 0;
                    break;
                }
            }
            res.push_back(drop);
        }
        return res;
    }
};

发表于 2020-04-28 11:42:39 回复(0)

C/C++

nbgao

class Solution {
public:
    /**
     * 远亲不如近邻
     * @param n int整型 居民个数
     * @param m int整型 方案个数
     * @param a int整型vector 居民的位置
     * @param x int整型vector 方案对应的位置
     * @return int整型vector
     */
    vector<int> solve(int n, int m, vector<int>& a, vector<int>& x) {
        vector<int> v;
        sort(a.begin(), a.end());
        for(int i=0;i<m;i++){
            int l=0, r=n-1, d=INT_MAX;
            while(l<=r){
                int mid = l + (r-l)/2;
                if(abs(a[mid]-x[i]) < d)
                    d = abs(a[mid]-x[i]);
                if(a[mid] == x[i])
                    break;
                else if(a[mid] < x[i])
                    l = mid+1;
                else
                    r = mid-1;
            }
            v.push_back(d);
        }
        return v;
    }
};

发表于 2020-07-04 21:16:36 回复(0)

Java

Jasonkay

排序, 然后二分查找插入位置即可.

    public int[] solve(int n, int m, int[] a, int[] x) {
        if (n <= 0) return new int[0];

        int[] res = new int[m];
        Arrays.sort(a);
        for (int i = 0; i < m; ++i) {
            int insertIndex = Arrays.binarySearch(a, x[i]);
            if (insertIndex < 0) {
                insertIndex = -insertIndex - 1;
                if (insertIndex == 0) res[i] = Math.abs(x[i] - a[0]);
                else if (insertIndex == n) res[i] = Math.abs(x[i] - a[n - 1]);
                else res[i] = Math.min(a[insertIndex] - x[i], x[i] - a[insertIndex - 1]);
            }
        }
        return res;
    }

发表于 2020-03-30 18:15:50 回复(3)

Python 3

牛客844991771号

class Solution:
    def solve(self , n , m , a , x ):
        # write code here
        dis1 = []
        dis2 = []
        dis = []
        for i in range(0, m):
            for ii in range(0, n):
                d = abs(x[i] - a[ii])
                dis1.append(d)
            dis2 = min(dis1)
            dis1 = []
            dis.append(dis2)
        return dis

没人写python的，本萌新来贴一个

发表于 2021-09-10 20:08:08 回复(0)

相遇的人再相遇

主要就是找插入位置，然后判断插入值和插入点相邻值的距离的最小值
先排序，然后用lower_bound找到第一个大于等于目标值的下标，然后根据下标来做进一步
判断处理计算。

class Solution {
public:
    /**
     * 远亲不如近邻
     * @param n int整型 居民个数
     * @param m int整型 方案个数
     * @param a int整型vector 居民的位置
     * @param x int整型vector 方案对应的位置
     * @return int整型vector
     */
    vector<int> solve(int n, int m, vector<int>& a, vector<int>& x) {
        vector<int> res;
        sort(a.begin(),a.end());
        for(int i=0;i<m;i++){
            auto it=lower_bound(a.begin(), a.end(), x[i]);
            int val;
            if(it==a.end()||it==(a.end()--)){
                val=x[i]-a[a.size()-1];
            }
            else if(it==a.begin()||it==(a.begin()++)){
                val=a[0]-x[i];
            }
            else {
                val=min(abs(x[i]-*(it--)),abs(*it-x[i]));
            }
            res.push_back(val);
        }
        return res;
    }
};

发表于 2020-09-28 23:17:34 回复(0)

Java

绵绵不加冰

import java.util.*;

public class Solution {
    /**
     * 远亲不如近邻
     * @param n int整型 居民个数
     * @param m int整型 方案个数
     * @param a int整型一维数组 居民的位置
     * @param x int整型一维数组 方案对应的位置
     * @return int整型一维数组
     */
    public int[] solve (int n, int m, int[] a, int[] x) {
        // write code here
        Arrays.sort(a);
        int[] res = new int[m];
        for(int i = 0;i < m;i++){
            res[i] = getRes(a,x[i]);
        }
        return res;
    }
    public static int getRes(int[] arr,int target){
        int nearest = Math.min(Math.abs(arr[0] - target),Math.abs(arr[arr.length - 1] - target));
        int l = 0,r = arr.length - 1;
        int mid = (l + r) / 2;
        nearest =Math.abs( Math.min(Math.abs(arr[mid] - target),nearest));
        while(l < r){
            if(arr[mid] > target){
                r = mid - 1;
            }else if(arr[mid] < target){
                l = mid + 1;
            } else{
                return 0;
            }
            mid = (l + r) / 2;
            nearest =Math.abs( Math.min(Math.abs(arr[mid] - target),nearest));
        }
        nearest = Math.abs(Math.min(nearest,Math.abs(arr[l] - target)));
        return nearest;
    }
}

发表于 2020-08-05 22:07:57 回复(0)

Java

余生满琳琅

import java.util.*;   
public class Solution { 
public static void main(String[] args) {
  int[] a= {175202325,305348361,18225345,1076950,259307096};  
  int[] x={-435704854,-196047871,-40657348,-638779837,289329995};
  Arrays.sort(a);
  int z[]=solve(5,5,a,x);
  System.out.println(Arrays.toString(z)); 
} 
/** * 远亲不如近邻  
* @param n int整型 居民个数  
* @param m int整型 方案个数  
* @param a int整型一维数组 居民的位置  
* @param x int整型一维数组 方案对应的位置  * @return int整型一维数组  
*/  
public static int[] solve(int n, int m, int[] a, int[] x) {
   // write code here
   int[] re=new int[m];
   TreeSet ts=new TreeSet();  
   //有序集合 
    for (int i = 0; i ; i++) {
            ts.add(a[i]);
    } 
    for (int i = 0; i ; i++) { 
       if(x[i]>=a[n-1]){
            re[i]=x[i]-a[n-1];
        } else if(x[i]0]){
             re[i]=a[0]-x[i];
         }else{
            int hi=ts.ceiling(x[i]);//>= 
            int lo=ts.lower(x[i]);//<
            re[i]=(hi-x[i]);
          }

    }
    return re;
  }
}

编辑于 2020-08-03 10:17:33 回复(0)

钢琴手1720

吃大亏！我看例子里的vector<int> a是排序的，没想到是没排序的

class Solution {
public:
    /**
     * 远亲不如近邻
     * @param n int整型 居民个数
     * @param m int整型 方案个数
     * @param a int整型vector 居民的位置
     * @param x int整型vector 方案对应的位置
     * @return int整型vector
     */
    int binSearch(vector<int>&a , int b){
        int len=a.size();
        int l=0;
        int r=len-1;
        int m=0;
        bool find=false;
        while(r>l){
            m=(r+l)>>1;
            if(a[m]>b)
                r=m-1;
            else if(a[m]<b)
                l=m+1;
            else{
                find=true;
                break;
            }
        }
        if(find)
            return 0;
        else{
            if(a[l]>b){
                if(l!=0)
                    return min(a[l]-b,b-a[l-1]);
                else
                    return a[0]-b;
            }else{
                if(l!=len-1)
                    return min(b-a[l],a[l+1]-b);
                else
                    return b-a[len-1];
            }
        }
    }
        
    vector<int> solve(int n, int m, vector<int>& a, vector<int>& x) {
        // write code here
        sort(a.begin(),a.end());
        vector<int> dis;
        for(auto &c:x){
            dis.push_back(binSearch(a, c));
        }
        return dis;
    }
};

发表于 2020-07-24 13:43:04 回复(0)

ccf123

class Solution {
public:
    /**
     * 远亲不如近邻
     * @param n int整型 居民个数
     * @param m int整型 方案个数
     * @param a int整型vector 居民的位置
     * @param x int整型vector 方案对应的位置
     * @return int整型vector
     */
    vector<int> solve(int n, int m, vector<int>& a, vector<int>& x) {
        vector<int> res;
        // write code here
        sort(a.begin(),a.end());
        for(auto c:x){
         res.push_back(getMindistance(n,a,c));
        }
        return res;
    }
    
    int getMindistance(int n, vector<int>& a,int c){
        int start=0;
        int end=n;
        while(start!=end){
           
           int mid=start+(end-start)/2;
           if(c<a[mid]){
            if(mid-1<start){
             return a[mid]-c;
              
            }else{
              if(a[mid-1]<=c){
               return min(c-a[mid-1],a[mid]-c);
               
              }else{
                  end=mid;
              }
            }
           }else if(c>a[mid]){
               if(mid+1>=end){
                  return c-a[mid];
               }else{
                if(a[mid+1]<c){
                 start=mid+1;
                }else{
                   return  min(c-a[mid],a[mid+1]-c);                   
                }
               }
           }else {
            return 0;
           }
           
            
        }
    }
};

编辑于 2020-05-21 08:20:39 回复(0)

C/C++

lllx123

二分查找
class Solution {
private:
	vector<int> res;
public:
	vector<int> solve(int n, int m, vector<int>& a, vector<int>& x) {
		sort(a.begin(), a.end());
		for (int i = 0; i < m; i++)
			res.push_back(binary_search(a, x[i]));
		return res;
	}
	
	int binary_search(vector<int> &a, int target)
	{
		int left = 0, right = a.size() - 1;
		while (left <= right)
		{
			int mid = (left + right) / 2;
			if (a[mid] == target)
				return 0;
			else if (a[mid] < target)
				left = mid + 1;
			else
				right = mid - 1;
		}
		int min_num = INT_MAX;
		for (int i = left - 1; i <= left + 1; i++)
		{
			if (i < a.size() && i >= 0)
				min_num = min(min_num, abs(target - a[i]));
		}
		return min_num;
	}

};

发表于 2020-04-18 21:04:03 回复(0)