Why is solution unaccepted as exceeds time limit - using Quicksort and Linear time search


  • 0
    V
    void quickSort(int *A, int l, int r, int *B) {
    
    	int pivot = A[l], i=l+1, j=r, tmp;
    
    	while(i<=j) {
    		while(A[i] < pivot) i++;
    		while(A[j] > pivot) j--;
    		if(i<=j) {
    			tmp = A[i];
    			A[i] = A[j];
    			A[j] = tmp;
    			tmp = B[i];
    			B[i] = B[j];
    			B[j] = tmp;
    			i++;
    			j--;
    		}
    	}
    
    	tmp = A[l];
    	A[l] = A[j];
    	A[j] = tmp;
    	tmp = B[l];
    	B[l] = B[j];
    	B[j] = tmp;
    
    	if(j-1>l) quickSort(A, l, j-1, B);
    	if(j+1<r) quickSort(A, j+1, r, B);
    
    }
    
    int* twoSum(int* nums, int numsSize, int target) {
    
    	int i=0, j=numsSize-1, sum=0, k=0;
    
    	int *index;
    	index = malloc(numsSize*sizeof(int));
    	for(k=0; k<numsSize; k++) index[k]=k+1;
    
    	quickSort(nums, 0, numsSize-1, index);
    	int *indices = malloc(2*sizeof(int));
    	indices[0] = indices[1] = -1;
    
    	sum = nums[i]+nums[j];
    	while(i<j) {
    		if(sum==target) {
    			indices[0] = index[i];
    			indices[1] = index[j];
    			free(index);
    			return indices;
    		}
    		else if(sum<target) {
    			i++;
    			sum = nums[i]+nums[j];
    		}
    		else {
    			j--;
    			sum = nums[i]+nums[j];
    		}
    	}
    
    	return indices;
    
    }

Log in to reply
 

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