Given a non-negative integer array, Find the minimum distance between 2 distinct elements of A.
Minimum Distance is defined as if P != Q then |(A[P] – A[Q])|
Solution:
#include <limits.h>
void merge_sort(int[], int, int);
int solution(int A[], int N) {
// write your code in C90
// Apply merge sort (takes O(nlogn))
merge_sort(A, 0, N-1);
// Loop will take O(n) hence total time in O(nlogn)
int min_dist = INT_MAX;
int dist = 0;
int i;
for(i = 1; i < N; i++)
{
dist = A[i] - A[i - 1];
if (min_dist > dist)
{
min_dist = dist;
}
}
return min_dist;
}
#define SIZE 1000000
void merge(int arr[],int min,int mid,int max)
{
int tmp[SIZE];
int i,j,k,m;
j = min;
m = mid+1;
for(i = min; j <= mid && m <= max ; i++)
{
if(arr[j] <= arr[m])
{
tmp[i] = arr[j];
j++;
}
else
{
tmp[i] = arr[m];
m++;
}
}
if(j > mid)
{
for(k = m; k <= max; k++)
{
tmp[i] = arr[k];
i++;
}
}
else
{
for(k = j; k <= mid; k++)
{
tmp[i] = arr[k];
i++;
}
}
for(k = min; k <= max; k++)
arr[k] = tmp[k];
}
void merge_sort(int arr[],int min,int max)
{
int mid;
if(min < max)
{
mid = (min + max)/2;
merge_sort(arr, min, mid);
merge_sort(arr, mid+1, max);
merge(arr, min, mid, max);
}
}
Time Complexity: O(N)
It should be O(N)
public static void minDistance( int []a, int x, int y) {
int minDistance = Integer.MAX_VALUE;
int firstIndex = -1;
for( int i = 0; i < a.length; ++i) {
if( a[i] == x || a[i] == y) {
if( firstIndex == -1 ) {
firstIndex = i;
} else {
if( a[i] != a[firstIndex]) {
int min = i – firstIndex;
if( min < minDistance) {
minDistance = min;
}
}
firstIndex = i;
}
}
}
System.out.println( "Min Distance: " + minDistance);
}
Hey Chao,
Could you please explain what is x and y here.
import java.io.PrintWriter;
public class MinDistance
{
public static int findMinDistance(int [] arr){
int length = arr.length;
int smallest = Integer.MAX_VALUE -1;
int smaller = Integer.MAX_VALUE;
for(int i =0; i<length;i++){
if(arr[i] <= smallest){
smaller = smallest;
smallest = arr[i];
}
else if(arr[i] <smaller) {
smaller = arr[i];
}
}
return smaller – smallest;
}// findMinDistance(int [] arr)
public static void main(String[] args)
{
PrintWriter pen = new PrintWriter(System.out,true);
int [] arr = {1,2,0,8,1,9,9,3};
int result = findMinDistance(arr);
pen.println(result);
}
}//class MinDistance