CareerCup

what i think is 1)computer all points' distance to the given point, and put them in an array
2) find the kth element in the array in O(n) time on average, by choosing a pivot from the array and then put all smaller elements in front of the pivot and all larger ones after it, just as quicksort. if # of smaller/equal elements <k, we find the element with rank=( k - # of smaller /equal elements) in the array after the pivot, and discard the other half. Do this recursively.
#include<iostream>
#include<math.h>
using namespace std;

struct point{
int x;
int y;
};

int * computedistance(point * set, int n)
{
int *a =new int[n];
for(int i=0;i<n;i++)
{

a[i]=(int)pow((double)set[i].x,2)+(int)pow((double)set[i].y,2);
}
return a;
}
void swap(int *a, int i, int j)
{
int temp=a[i];
a[i]=a[j];
a[j]=temp;
}

int findkth(int * a, int size, int k)
{
if(size==1)
{
return a[0];
}
int pivot=a[size/2];
swap(a,0,size/2);
int left=1;
int right=size-1;
while(left<right)
{
while(a[left]<=pivot&&left<right)
left++;
while(a[right]>=pivot&&left<right)
right--;
swap(a,left,right);
}
int bound;
if(a[left]<=pivot)
{
bound=left;
}
else
{
bound=left-1;
}
swap(a,0,bound);
if(bound==k)
return a[bound];
else if(bound>k)
findkth(a,bound,k);
else
findkth(a+bound+1,size-bound-1,k-(bound+1));
}

void main()
{
point p;
p.x=1;
p.y=2;

int x[]={7,2,4,5,6,4,7};
int y[]={2,3,4,5,6,7,9};
int n=sizeof(x)/sizeof(int);
point * set=new point[n];
for(int i=0;i<n;i++)
{
set[i].x=x[i]-p.x;
set[i].y=y[i]-p.y;
}
int k=1;
int *a=computedistance(set, n);
for(int i=0;i<n;i++)
cout<<a[i]<<" ";

int r=findkth(a, n, k-1);
double result=sqrt((double) r);
cout<<result<<endl;
}

Rather than sorting u can create the min heap with those distance in O(n)
And then u can exatract min k time .... well this will give (O(n) + klogn)


The other way is to find first k node(distance) is using variation of quick sort ..... this can be done in O(n) .... check out careercup.com/question?id=4356905

use a max heap.. of size k.. in O(n) add each of the distances to the max heap..
maintain the size as k, by adding the new element and removing the maximum element..(the top of heap) ...
all the heap properties ll be done in O(k log k) time..
if k is O(n).. (// assumed to be a big number approx to n)
then the total complexity is O(n log n)..
else if k is a small number , it could be argued for the complexity to be O(n + k log k) = O(n).

- Create an array of size k, call it mins
- While computing distances of each of n points from B, keep the minimum ones sorted in the array mins.
- At the end you will have the kth distant point in the kth element of the array mins.
O(n*k)

create a k-d tree
it is a data structure used specifically to find n nearest neighbors and u store the squared distance at each node

maintain two heap, one max heap takes care of first k, one min heap takes care of rest.

Finding Kth order statistic is O(n) when you do something like "partition" part of quick sort. So find all distances and find the Kth order statistic - O(n) time.

previously calculate the distance and then put into the array. and apply the quickselect algorithm to find the kth smallest elements.

We may use randomized divide and conquer, the time complexity of which should be O(n).

quick select alg is ok for that.