import java.util.Arrays;
import java.util.Random;
public class ClosestPair {
public static void main(String[] argv){
Random random = new Random();
int[] nums = new int[10];
for(int i = 0; i< 10; i++) {
nums[i]= random.nextInt(1000);
}
ClosestPair closestPair = new ClosestPair();
int[] pair = closestPair.closestPair(nums);
System.out.println(Arrays.toString(pair));
}
/*
Problem: Given sorted array find the closest pair of elements
Solution: First sort the array then perform a linear search with 2 elements at a time to find out
difference between n and n-1 while maintaining smallest difference
*/
public int[] closestPair(int[] nums){
Arrays.sort(nums);
int minDiff = Integer.MAX_VALUE;
int[] closestPair = new int[2];
for(int i = 1; i < nums.length; i++){
int diff = Math.abs(nums[i]-nums[i-1]);
if(diff <minDiff){
closestPair[0] = nums[i-1];
closestPair[1] = nums[i];
minDiff = diff;
}
}
return closestPair;
}
}
Monday, July 24, 2017
Closest Pair of elements in sorted array
Labels:
array,
designmanual
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment