Question

In class we wrote a method closestPairFast that on an input array of numbers, finds the distance of the closest pair by first sorting the input array and then finding the closest adjacent pair. (See the file ClosestPair1D.java in the Code folder on D2L.) In this problem, you are asked to modify the method so that it returns an integer array consisting of the indices of the closest pair in the original array. If there is a tie, just return the indices of an arbitrary closest pair. The skeleton for the new method, closestPairFast2, is provided in the file Hw1_p2.java in the Homework Files folder.

The following is a sample run:

Input:   8 15 19 3 12

Return value:   1 4

Explanation: The closest pair is (15, 12). The indices of 15 and 12 in the original array are 1 and 4 respectively.

The method closestPairFast2 should have the same structure as closestPairFast and have time complexity ?(?????), where ? is the length of the input array.

Hint: Define a helper class consisting of two attributes: (1) the value of an element and (2) its index in the original input array. Have the class implement the Comparable interface so that you can sort by value and keep the original indices.

public class Hw1_p2_updated {
   // HW1 Problem 2
   public static int[] closestPairFast2(long[] A) {
       int[] ans = new int[2];
       int n = A.length;
       ValIndexPair[] B = new ValIndexPair[n];
       for (int i = 0; i < n; i++) {
           B[i] = new ValIndexPair(A[i], i);
       }
      
       Arrays.sort(B);
      
       // Your code starts
      
      
       // Your code ends
      
       return ans;
   }
  
   public static void main(String[] args) {
       // Test driver for closestPairFast2
       int n = 5;
       long[] A = new long[n];
       for (int i = 0; i < n; i++) {
           A[i] = (long) (Math.random() * 100);
           System.out.print(A[i] + " ");
       }
       System.out.println("\n");
       closestPairFast2(A);
      
   }
}

class ValIndexPair implements Comparable<ValIndexPair> {
   long val;
   int idx;
  
   ValIndexPair(long val, int idx) {
       this.val = val; this.idx = idx;
   }
  
   public int compareTo(ValIndexPair o) {
       if (this.val < o.val) return -1;
       else if (this.val == o.val) return 0;
       else return 1; // this.val > o.val
   }
}

Answer 1

import java.util.*;
public class Main {
// HW1 Problem 2
public static int[] closestPairFast2(long[] A) {
int[] ans = new int[2];
int n = A.length;
ValIndexPair[] B = new ValIndexPair[n];
for (int i = 0; i < n; i++) {
B[i] = new ValIndexPair(A[i], i);
}
  
Arrays.sort(B);
// System.out.println(Arrays.toString(B));
// Your code starts
long min=B[1].val-B[0].val;
// int min_index=1;
for(int i=0;i<n-1;i++){
if(min>B[i+1].val-B[i].val){
min=B[i+1].val-B[i].val;
// min_index=i+1;
ans[0]=B[i].idx;
ans[1]=B[i+1].idx;
}
}
  
// Your code ends
return ans;
}
  
public static void main(String[] args) {
// Test driver for closestPairFast2
int n = 5;
long[] A = new long[n];
for (int i = 0; i < n; i++) {
A[i] = (long) (Math.random() * 100);
System.out.print(A[i] + " ");
}
System.out.println("\n");
int[] temp=closestPairFast2(A);
System.out.println(temp[0]+" "+temp[1]);
}
}

class ValIndexPair implements Comparable<ValIndexPair> {
long val;
int idx;
  
ValIndexPair(long val, int idx) {
this.val = val; this.idx = idx;
}
  
public int compareTo(ValIndexPair o) {
if (this.val < o.val) return -1;
else if (this.val == o.val) return 0;
else return 1; // this.val > o.val
}
}