import java.util.Arrays; public class ClosestPair1D { public static long closestPairSlow(long[] A) { long min = Long.MAX_VALUE; int n = A.length; for (int i = 0; i < n-1; i++) { for (int j = i+1; j < n; j++) { long d = Math.abs(A[i] - A[j]); if (d < min) min =d; } } return min; } public static long closestPairFast(long[] A) { long min = Long.MAX_VALUE; Arrays.sort(A); for (int i = 0; i < A.length-1; i++) { long d = Math.abs(A[i] - A[i+1]); if (d < min) min =d; } return min; } public static void main(String[] args) { int n = 500000; long[] A = new long[n]; for (int i = 0; i < n; i++) { A[i] = (long) (Math.random() * (1L << 60)); //System.out.print(A[i] + " "); } System.out.println(); System.out.println("closestPairFast:"); long tic2 = System.currentTimeMillis(); long minDist2 = closestPairFast(A); long toc2 = System.currentTimeMillis(); System.out.printf("Minimum distance: %d ", minDist2); System.out.printf("Time: %.2f seconds ", (double)(toc2-tic2)/1000); System.out.println(" closestPairSlow:"); long tic = System.currentTimeMillis(); long minDist = closestPairSlow(A); long toc = System.currentTimeMillis(); System.out.printf("Minimum distance: %d ", minDist); System.out.printf("Time: %.2f seconds ", (double)(toc-tic)/1000); } }

import java.util.Arrays; import java.util.Scanner;

public class Hw3_p1 { // HW7 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) { Scanner input = new Scanner(System.in); System.out.print("Enter the number of values: "); int n = input.nextInt(); long[] A = new long[n]; System.out.print("Enter the values: "); for (int i = 0; i < A.length; i++) { A[i] = input.nextLong(); }

int[] pairIndice = closestPairFast2(A); System.out.println(" The two values are closest are at indice " + pairIndice[0] + " and " + pairIndice[1]);

} }

class ValIndexPair implements Comparable { 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 } }

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 ClosestPair1D.java above). 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, return the closest pair with the smallest values. The skeleton for the new method, closestPairFast2, is provided in the file Hw3_p1.java.

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 in the attached ClosestPair1D.java 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.

in java code