lintcode 387. 最小差

太过爱你忘了你带给我的痛 2023-07-07 15:56 30阅读 0赞

给定两个整数数组（第一个是数组 A，第二个是数组 B），在数组 A 中取 A\[i\]，数组 B 中取 B\[j\]，A\[i\] 和 B\[j\]两者的差越小越好(|A\[i\] - B\[j\]|), 返回最小差。

样例
    样例 1:
    
    输入: A = [3, 6, 7, 4], B = [2, 8, 9, 3] 
    输出: 0
    解释: A[0] - B[3] = 0
    样例 2:
    
    输入: A = [1, 2, 3, 4], B = [7, 6, 5]
    输出: 1
    解释: B[2] - A[3] = 1
    挑战
    时间复杂度 O(n log n)

思路：  
1、先对两个数组进行排序  
2、遍历A数组  
3、接着利用二分查找B数组找出第一个大于或等于A中的位置  
这里有三种可能：

*  B中没有比A【i】大的数，这时候最小差来自于A【i】与B的最后一个数的差的绝对值
 *  B中所有的值比A【i】大，这时候最小差来自于A【i】与B的第一个数的差的绝对值
 *  B中有的值比A【i】大，有的小，找到第一个大于A【i】的值，比较B【i】，B【i-1】和A【i】的大小

class Solution {
        
    public:
        /**
         * @param A: An integer array
         * @param B: An integer array
         * @return: Their smallest difference.
         */
        int smallestDifference(vector<int> &A, vector<int> &B) {
        
            // write your code here
            sort(A.begin(),A.end());
            sort(B.begin(),B.end());
            int res=INT_MAX;
            for (int i = 0; i < A.size(); i++) {
        
                int index=lower_bound(B.begin(),B.end(),A[i])-B.begin();
                if(index==B.size()) res=min(res,A[i]-B[index-1]);
                else if(index!=0) res=min(res,min(B[index]-A[i],A[i]-B[index-1]));
                else res=min(res,B[index]-A[i]);
            }
            return res;
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，30人围观）

还没有评论，来说两句吧...

相关阅读

相关 lintcode400. 最大间距

给定一个未经排序的数组, 请找出这个数组排序之后的两个相邻元素之间最大的间距. 如果数组中少于 2 个元素, 返回 0. 样例样例 1:

叁歲伎倆/ 2023年07月07日 15:59/ 0 赞/ 660 阅读

相关 lintcode 387. 最小差

给定两个整数数组（第一个是数组 A，第二个是数组 B），在数组 A 中取 A\[i\]，数组 B 中取 B\[j\]，A\[i\] 和 B\[j\]两者的差越小越好(|A\[i

太过爱你忘了你带给我的痛/ 2023年07月07日 15:56/ 0 赞/ 31 阅读

相关 lintcode 184. 最大数

给出一组非负整数，重新排列他们的顺序把他们组成一个最大的整数。样例样例 1: 输入:[1, 20, 23, 4, 8] 输出:"

红太狼/ 2023年07月06日 13:23/ 0 赞/ 43 阅读

相关 lintcode91. 最小调整代价动态规划

给一个整数数组，调整每个数的大小，使得相邻的两个数的差不大于一个给定的整数target，调整每个数的代价为调整前后的差的绝对值，求调整代价之和最小是多少。样例

末蓝、/ 2023年07月04日 14:08/ 0 赞/ 59 阅读

相关 lintcode 761. 最小子集

给一非负整数数组. 取数组中的一部分元素, 使得它们的和大于数组中其余元素的和, 求出满足条件的元素数量最小值. 样例例1: 输入:

灰太狼/ 2023年05月22日 12:28/ 0 赞/ 40 阅读

相关 lintcode724. 最小划分

给出一个正整数数组，写一个程序把这个整数数组分成S1跟S2两部分，使S1中的和跟S2中的和的差的绝对值最小。换句话讲，如果有一个一个整数数组 S 有 n 个数，如果Subset

阳光穿透心脏的1/2处/ 2023年05月21日 15:29/ 0 赞/ 97 阅读

相关【LintCode 简单】155. 二叉树的最小深度

1.问题描述：给定一个二叉树，找出其最小深度。二叉树的最小深度为根节点到最近叶子节点的最短路径上的节点数量。 2.样例： > 样例 1: > > 输入: \

梦里梦外;/ 2022年11月27日 00:44/ 0 赞/ 248 阅读

相关 leetcode1200. 最小绝对差

给你个整数数组 arr，其中每个元素都不相同。请你找到所有具有最小绝对差的元素对，并且按升序的顺序返回。示例 1：输入：arr = \[4,2,1,3\] 输

太过爱你忘了你带给我的痛/ 2022年10月15日 00:44/ 0 赞/ 166 阅读

相关最小方差生成树（Kruskal）

问题描述给定带权无向图，求出一颗方差最小的生成树。输入格式输入多组测试数据。第一行为N,M，依次是点数和边数。接下来M行，每行三个整数U,V,W，代表连接U,V的边

偏执的太偏执、/ 2022年09月29日 15:51/ 0 赞/ 203 阅读

相关【lintcode】最大子数组

题目描述：给定一个整数数组，找到一个具有最大和的子数组，返回其最大和。子数组最少包含一个数样例给出数组[−2,2,−3

￡神魔★判官ぃ/ 2022年06月02日 21:08/ 0 赞/ 286 阅读