Does any one have C solution which is less than O(n2), I met time limit problem. (without advance data structure)


  • 0
    D

    Does any one have C solution which is less than O(n2), I met time limit problem. (without advance data structure)


  • 0
    D

    I answer myself.

    Use quick sort along with reorganised index list can make it O(lgN).

    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;
    

    }


Log in to reply
 

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