远亲不如近邻

[编程题]远亲不如近邻

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

算法知识视频讲解

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)

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)