[LintCode] The Smallest Difference

Scorpion 发布于2019-08-14 15:19 / 3339人阅读

摘要：先对，排序，然后分别赋指针，。以两个指针都不越界为条件遍历。若，更新当前差值，反之，则更新差值并令。

Problem

Given two array of integers(the first array is array A, the second array is array B), now we are going to find a element in array A which is A[i], and another element in array B which is B[j], so that the difference between A[i] and B[j] (|A[i] - B[j]|) is as small as possible, return their smallest difference.

Example

For example, given array A = [3,6,7,4], B = [2,8,9,3], return 0

Note

先对A，B排序，然后分别赋指针p1，p2。以两个指针都不越界为条件遍历。若p1 <= p2，更新当前差值，p1++；反之，则更新差值并令p2++。

Solution

public class Solution {
    public int smallestDifference(int[] A, int[] B) {
        int p1 = 0, p2 = 0;
        Arrays.sort(A);
        Arrays.sort(B);
        int res = Integer.MAX_VALUE;
        while (p1 < A.length && p2 < B.length) {
            if (A[p1] <= B[p2]) {
                res = Math.min(res, B[p2] - A[p1]);
                p1++;  
            }
            else {
                res = Math.min(res, A[p1] - B[p2]);
                p2++;
            }
        }
        return res;
    }
}

服务器托管海外云主机 Difference Smallest LintCode the

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65617.html

[LintCode] Kth Smallest Number in Sorted Matrix

Problem Find the kth smallest number in at row and column sorted matrix. Example Given k = 4 and a matrix: [ [1 ,5 ,7], [3 ,7 ,8], [4 ,8 ,9], ] return 5 Challenge O(k log n), n is the maximal n...

mgckid 2019-08-14 15:45 评论0 收藏0
[LintCode] Build Post Office I & II

Build Post Office Problem Given a 2D grid, each cell is either an house 1 or empty 0 (the number zero, one), find the place to build a post office, the distance that post office to all the house sum i...

1treeS 2019-08-14 15:50 评论0 收藏0
[LintCode] Minimum Absolute Difference in BST

Problem Minimum Absolute Difference in BSTGiven a binary search tree with non-negative values, find the minimum absolute difference between values of any two nodes. Example Input: 1 3 ...

curlyCheng 2019-08-16 12:36 评论0 收藏0
[LintCode/LeetCode] Contains Duplicate III

Problem Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute dif...

MageekChiu 2019-08-19 10:48 评论0 收藏0
[LintCode/LeetCode] Contains Duplicate II

Problem Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at ...

894974231 2019-08-19 10:48 评论0 收藏0