資訊專欄INFORMATION COLUMN
摘要：先對(duì)，排序，然后分別賦指針，。以兩個(gè)指針都不越界為條件遍歷。若，更新當(dāng)前差值，反之，則更新差值并令。
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.
ExampleFor example, given array A = [3,6,7,4], B = [2,8,9,3], return 0
Note先對(duì)A，B排序，然后分別賦指針p1，p2。以兩個(gè)指針都不越界為條件遍歷。若p1 <= p2，更新當(dāng)前差值，p1++；反之，則更新差值并令p2++。
Solutionpublic 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;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/65617.html
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...
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...
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 ...
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...
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 ...
閱讀 1529·2021-11-18 10:02
閱讀 1680·2021-09-04 16:40
閱讀 3180·2021-09-01 10:48
閱讀 882·2019-08-30 15:55
閱讀 1860·2019-08-30 15:55
閱讀 1379·2019-08-30 13:05
閱讀 3022·2019-08-30 12:52
閱讀 1632·2019-08-30 11:24
