题解 | #远亲不如近邻#

远亲不如近邻

http://www.nowcoder.com/practice/1b2c9a2ba11746958036b29f2e9ee72b

题目描述
牛牛最近搬到了一座新的城镇,这个城镇可以看成是一个一维的坐标系。城镇上有n个居民,第i个居民的位置为ai。现在牛牛有m个搬家方案,在第i个方案中他会搬到位置xi。

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

方法一:暴力解法

求解思路
对于求解本题,我们对每个方案的位置,求出所有居民位置,即可得到本题目的答案。

图片说明

解题代码

class Solution {
public:
  vector<int> solve(int n, int m, vector<int> a, vector<int> x)
  {
    vector<int> myt(m); // 声明数组
    for(int i = 0; i < m; ++i)
    {
        myt[i] = 2e9;
        for(int j = 0; j < n; ++j) myt[i] = min(myt[i], abs(x[i]-a[j])); // 更新结果
    }
      return myt; // 返回结果
  }
};

复杂度分析
时间复杂度:两层循环,因此时间复杂度为(图片说明 )
空间复杂度:没有引入额外的内存地址空间,因此空间复杂度为

方法二:优化求解

求解思路
对于本问题,我们可以对所有居民的位置进行排序,然后对每个方案进行讨论,找到中间位置,和其相邻的两个数,并计算其距离。

图片说明

解题代码

class Solution {
public:
  vector<int> solve(int n, int m, vector<int> a, vector<int> x)
  {
    sort(a.begin(), a.end()); // 快排
    vector<int> t(m);
    for(int i = 0; i < m; ++i)
    {
        int myval = x[i];
        int myans = 2e9;
        if(myval < a[0])
            myans = a[0]-myval; // 记录返回值
        else
        {
            int l = 0, r = n-1;
            while(l <= r)
            {   //二分法的思想
                int mid = (r+l)>>1;
                if(a[mid] <= myval)
                {
                    myans = min(myans, myval-a[mid]); 
                    l = mid+1;
                }
                else
                    r = mid-1;
            }
        }
        if(myval > a[n-1])
            myans = min(myans, myval-a[n-1]);
        else
        {
            int l = 0, r = n-1;
            while(l <= r)
            {   //二分法的思想
                int mid = (r+l)>>1;
                if(a[mid] >= myval){myans = min(myans, a[mid]-myval); r = mid-1;}
                else l = mid+1;
            }
        }
        t[i] = myans;
    }
      return t; // 返回结果即可
}
};

复杂度分析
时间复杂度:使用二分法,因此时间复杂度为
空间复杂度:引入常数级变量空间,因此空间复杂度为

算法 文章被收录于专栏

算法题的题解以及感受

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议