CareerCup

Is there any method to find max distance neighboring number where the array is integer array in O(n)?

don't understand the question.
"max disntance two numbers" means the absolute value of the difference, such as |a-b|?
"two neighbouring numbers" means, e.g., (x1,x2), (x2,x3), (x3,x4) and so on?

sorry, see an example
given x[]={2.0,1.0,9.0,-3.5}
then the answer is 7.0, because on the number axis, it is -3.5,1.0,2.0,9.0 from left to right.
distance between two neighbouring numbers are 1-(-3.5),2-1,9-2.
so the answer is 9-2=7
make sense?

I doubt if there is better than O(n logn) solution. It is related to array uniqueness problem. Look in Wikipedia.

Call first element the pivot

Find largest number > pivot and to the right of array. Call it A. If you cannot find one A = pivot
Find smallest number < pivot and to the right of array. Call it B. If you cannot find one B = pivot

Ans : A-B

Sort the array O(nlg(n)). Then in O(n) time i.e. single pass, you can get the maximum distance.

Heapify the array - takes O(n). Then since every node satisfies the heap property (for instance, so that every parent > children) find the max difference between each parent and its 2 children (which represent neighboring numbers) - again O(n). Overall: O(n).

there is an O(n) algorithm. use n bucket with the same size of (max-min)/(n-1) and hash each element into the corresponding bucket, then the maximum distance would >= (max-min)/(n-1), which would only appear in neighbor bucket (skipping empty buckets). then you know what to do.

just use count sort

code：

#include <cstdio>
#include <cstdlib>
#include <memory.h>
using namespace std;

int csort(int key[], int len)
{
	int *sort;
	int max = key[0];
	int min = key[0];
	int step = 0;
	int tmp = 0;
	for(int i = 0; i < len; i++)
	{
		if(key[i] >= max)
			max = key[i];
		if(key[i] <= min)
			min = key[i];
	}

	step = -min;

	for(int i = 0; i < len; i++)
	{
		key[i] = key[i] + step;
	}

	sort = (int *)malloc((max - min + 1)*sizeof(int));
	if(sort == NULL)
		printf("malloc error\n");
	memset((int *)sort, 0, (max - min + 1)*sizeof(int));

	for(int i = 0; i < len; i++)
	{
		sort[key[i]] = 1;
	}

	for(int i = 1; i<max - min + 1; i++)
	{
		sort[i] += sort[i-1];
	}
	
	for(int i = 0; i < max - min + 1; i++)
	{
		if(sort[i] == tmp)
			continue;
		else
		{
			key[sort[i]-1] = i;
			tmp = sort[i];
		}
	}

	for(int i = 0; i < len; i++)
	{
		key[i] = key[i] - step;
	}
        free(sort);
	sort = NULL;
	
	return 0;
}

int count_max(int key[], int len)
{
	int max = 0;
	for(int i = 1; i < len; i++)
	{
		if((key[i] - key[i-1]) >= max)
			max = key[i] - key[i-1];
	}
	return max;
}

int main()
{
	int key[10] = {3,7,9,8,-22,6,22,11};

	csort(key, 8);
	for(int i = 0; i < 8; i++)
		printf("%d ",key[i]);
	printf("\n");
	printf("The max distence is:%d\n",count_max(key,8));
	
}

public static void main(String[] args){
DistanceBetweenNo db = new DistanceBetweenNo();
double[] d_arr = {2.0,1.0,9.0,-3.5};
Arrays.sort(d_arr);
double max = d_arr[d_arr.length - 1] - d_arr[d_arr.length - 2];

System.out.println("Max difference: " + max);
}