Leetcode 1385. 两个数组间的距离值（DAY 174）---- 二分算法学习期

ゝ一纸荒年。 2022-09-12 12:43 83阅读 0赞

### 文章目录 ###

*   *  原题题目
     *  代码实现（首刷自解）

--------------------

## 原题题目 ##

--------------------

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATG92ZSA2_size_20_color_FFFFFF_t_70_g_se_x_16]

--------------------

## 代码实现（首刷自解） ##

--------------------

class Solution { 
    public:
        int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d) { 
            int ret = 0;
            sort(arr2.begin(),arr2.end());
            for(const auto& num:arr1)
            { 
                auto higher_one = upper_bound(arr2.begin(),arr2.end(),num);
                auto lower_one = lower_bound(arr2.begin(),arr2.end(),num);
                if((higher_one != arr2.end() && *higher_one - num <= d) || (lower_one != arr2.end() && abs(num - *lower_one) <= d))
                    continue;
                else
                { 
                    if(lower_one == arr2.begin() || abs(num - *(--lower_one) > d)) ++ret;
                }
            }
            return ret;
        }
    };

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATG92ZSA2_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/cfcd82bbe13748e4ae6db9c46d097fb6.png