I don't think my algorithm is better than others, but it's runtime is very short


  • 0
    X

    could anyone explain this?

    class Solution {
    public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        int len=nums.size();
        if(len==0)
            return false;
        
        vector<int> indexs;
        for(int i=0;i<len;i++)
            indexs.push_back(i);
        
        QSort(nums,indexs,0,len-1);
        
        for(int i=0;i<len-1;i++)
        {
            int j=i+1;
    		while(j<len&&(long long)nums[j]-(long long)nums[i]<=t)
    		{
    			if(abs(indexs[i]-indexs[j])<=k)
    				return true;
    			j++;
    		}
        }
        
        return false;
    }
    
    void QSort(vector<int>& nums,vector<int>& indexs,int s,int e)
    {
        if(s<e)
        {
            int mid=Partition(nums,indexs,s,e);
            QSort(nums,indexs,s,mid-1);
            QSort(nums,indexs,mid+1,e);
        }
    }
    
    int Partition(vector<int>& nums,vector<int>& indexs,int s,int e)
    {
        int prov=nums[s];
        int provindex=indexs[s];
        while(s<e)
        {
            while(s<e&&prov<=nums[e])
                e--;
            nums[s]=nums[e];
            indexs[s]=indexs[e];
            while(s<e&&prov>=nums[s])
                s++;
            nums[e]=nums[s];
            indexs[e]=indexs[s];
        }
        nums[s]=prov;
        indexs[s]=provindex;
        return s;
    }
    

    };


Log in to reply
 

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