Feeling confused about the requirement 'constant memory'


  • 7
    G

    I know most people use quick sort to solve this problem. But in fact the space complexity of the quick sort should be O(nlogn) because of the stack allocation(such as the return address pushed in the stack, local variables you used in recursion function).
    Actually, any divide-and-conquer approaches (like merge sort even for the in-place merge implementation, quick sort) for this problem requires more than constant memory. Without divide-and-conquer approach, the only way I know for sorting in O(nlogn) time is heap sort. Unfortunately, this solution is even worse than divide-and-conquer approach.

    There is some algorithm uses constant memory space like bubble sort, insertion sort ,etc. But the time complexity of none of them are O(nlogn).

    So I feel so confused about this, Is there any sorting algorithm we can use here to get a real constant memory complexity? But it seems impossible to me, so does anyone have ideas about this?


  • -2
    T
    This post is deleted!

  • -2
    T
    This post is deleted!

  • -2
    L

    use in-place merge sort, in-place means constant memory

    eg:

    class Solution {
    public:
    ListNode *sortList(ListNode *head) {
    	if( !head || !head->next ) return head;
    	int count_r=0;
    	ListNode *hr,*hl, *head2;
    	hr=hl=head;
    	while(1){
    		if( hr->next ){
    			count_r=0;
    			hr = hr->next;
    			count_r++;
    			if(hr->next){
    				hr = hr->next;
    				count_r++;
    			}
    
    			if( hl->next && count_r>1){
    				hl = hl->next;
    			}
    		}
    
    		if( !hr->next ){
    			break;
    		}
    	}
    
    	head2 = hl->next;
    	hl->next = NULL;
    	head = sortList(head);
    	head2 = sortList(head2);
    
    	ListNode *nhead = nodeCompareMove(head, head2);
    	hr = nhead;
    
    	while( head || head2){
    		hr->next = nodeCompareMove(head, head2);
    		hr = hr->next;
    	}
    
    	return nhead;
    }
    
    ListNode *nodeCompareMove(ListNode*& n1, ListNode*& n2){
    	ListNode *re;
    	if(n2 && n1){
    		if( n1->val>n2->val ){
    			re = n2;
    			n2 = n2->next;
    		}else{
    			re = n1;
    			n1 = n1->next;
    		}
    	}else if(n1){
    		re = n1;
    		n1 = NULL;
    	}else{
    		re = n2;
    		n2 = NULL;
    	}
    	return re;
    }
    

    };


  • 0
    L

    It seems in the code, you recursively called sortList(head) and sortList(head2), wouldn't that cost O(logn) memory space as return stack? I think quick sort would have the same problem, I'm not sure how this could be avoided. Could you explain that? Thanks!


  • 0
    W

    Using recursion the extra memory used I think should be O(n) instead of O(nlogn) though, since there are about
    1+2+4+8+...+n/2 or O(n) recursive calls.


  • 0
    L

    You are right, can't be 'constant memory' If include stack allocation, didn't read your question clearly enough.


  • 0

    quicksort is usually in O(logn) time, you can see this: http://en.wikipedia.org/wiki/Quicksort#Space_complexity
    it's not likely that O(1) space can be achieved for quicksort. however a well implemented merge sort makes this possible.


  • 0
    V

    I am afraid your complexities all spell O(nlogn) for some reason. To clarify:

                             Method |         Time   |    Space 
    
                  bubble / insertion    |      O(n^2)   |   O(1) 
    
                  merge / quick   (*)   |  O(n log(n)) | O(log(n))
    

    (*) both implemented using recursive function calls


  • 1
    J

    the space complexity of the quick sort is O(nlogn) only if it is the array, and it should be constant here, for ListNode.


Log in to reply
 

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