题解 | #远亲不如近邻#

题目关键点：
a数组元素是每个邻居在坐标上的位置（一维坐标），x数组元素是牛牛搬家之后在坐标上的位置
要求每次搬家后最近邻居的最近距离

方法一：暴力解法
枚举x数组和a数组，定义一个ans数组保存每轮循环中找到的x[i]与a[i]之差的最小绝对值

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
        int[]ans=new int[x.length];
        //枚举x[i]
        for(int i=0;i<x.length;i++){
            //找完一轮的最小值需要开始下一轮寻找时记得初始化min
            int min=Integer.MAX_VALUE;
            //枚举a[j]
            for(int j=0;j<a.length;j++)
               min=Math.min(Math.abs(x[i]-a[j]),min);//在a数组中找到离x[i]最近的，记录它们的差
            ans[i]=min; 
        }
        return ans;
    }
}

复杂度：
时间复杂度：双重循环，最坏时间复杂度为 $O(mn)$
空间复杂度：额外使用数组大小不超过m，空间复杂度为 $O(m)$

方法二：二分查找
寻找x[i]的插入位置，直接查找a数组的时间复杂度较高，我们可以使用二分查找
先对a数组排序,再枚举搬家方案x[i]:
在a数组中用二分法查找距离x[i]最近的元素，计算两数之差的绝对值

图片说明

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
        int[]ans=new int[x.length];
        //首先对a数组排序
        Arrays.sort(a);
        //枚举搬家方案x[i]
        for(int i=0;i<x.length;i++){
            //二分查找
            int l=0,r=a.length-1;
            int mid=(l+r)/2;
            //初始化最近距离的邻居为a[mid]，最近距离为它们的差的绝对值
            int min=Math.abs(a[mid]-x[i]);
            while(l<r){
                //在[mid+1,r]区间找
                if(x[i]>a[mid])l=mid+1;
                //在[l,mid-1]区间找
                else if(x[i]<a[mid])r=mid-1;
                //如果找到和x[i]相等的数，则最近距离为0
                else {min=0;break;}
                mid=(l+r)/2;
                //找到缩小区间的中间值并更新最小值
                min=Math.min(min,Math.abs(a[mid]-x[i]));
            }ans[i]=min;
        }
        return ans;
    }
}

复杂度：
时间复杂度：二分法的时间复杂度为 $图片说明$ ,整体时间复杂度为 $图片说明$
空间复杂度：ans数组的大小为m，空间复杂度为 $O(m)$