[LintCode] The Smallest Difference

Scorpion 發布于2019-08-14 15:19 / 3498人閱讀

摘要：先對，排序，然后分別賦指針，。以兩個指針都不越界為條件遍歷。若，更新當前差值，反之，則更新差值并令。

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;
    }
}

云服務器 GPU云服務器 Difference Smallest LintCode the

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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