8ms C solution Q(lgN) with quick sort, ugly but works

• ``````void Qsort(int *nums,int *IdxList,int sp, int ep)
``````

{
int i=sp,j=ep;
int x=nums[sp];
int x_idx=sp;
int org_idx=IdxList[sp];

if(sp<ep)
{
while(i<j)
{
while(i<j&&nums[j]>=x)j--;
if(i<j)
{
nums[x_idx]=nums[j];
IdxList[x_idx]=IdxList[j];
}

``````    while(i<j&&nums[i]<=x)i++;
if(i<j)
{
nums[j]=nums[i];
IdxList[j]=IdxList[i];
}
nums[i]=x;
IdxList[i]=org_idx;
x_idx=i;
}
Qsort(nums,IdxList,sp,x_idx-1);
Qsort(nums,IdxList,x_idx+1,ep);
``````

}
}

bool containsNearbyAlmostDuplicate(int* nums, int numsSize, int k, int t) {
int i,j;
long diff;
long step_dist=0;

``````if(numsSize==0)
return false;

int *IdxList=(int *)malloc(sizeof(int)*numsSize);

for(i=0;i<numsSize;i++)
IdxList[i]=i;

Qsort(nums,IdxList,0,numsSize-1);

for(i=1;i<numsSize;i++)
{
diff=(long)nums[i]-(long)nums[i-1];
step_dist+=diff;
if(step_dist<=(long)t&&abs(IdxList[i]-IdxList[0])<=k||diff<=(long)t&&abs(IdxList[i]-IdxList[i-1])<=k)
return true;
}
return false;
``````

}

• Can not be uglier than this shit !

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.