A solution by on C language with quicksort


  • 0
    9

    /*
    Seldom people use C to solve this question.
    So that I do one.
    I use quick sort to sort the array greed and size.
    The complexity is O(nlogn).
    Have a look if you need it. Thank you.
    */

    int partition(int* arr, int p, int r){
    int x = arr[r];
    int i = p - 1;
    int j, tmp;

    for (j = p; j <= r - 1; j++) {
    	if (arr[j] <= x) {
    		i = i + 1;
    		// exchange arr[i] <-> arr[j]			
    		tmp = arr[i];   arr[i] = arr[j];  arr[j] = tmp;
    	}
    }
    
    // exchange arr[i+1] <-> arr[r]
    tmp = arr[i+1];  arr[i+1] = arr[r];	arr[r] = tmp;
    
    return (i+1);
    

    }

    void quicksort(int* arr, int p, int r){
    int q;

    if (p < r) {
    	q = partition(arr, p, r);
    	quicksort(arr, p, q - 1);
    	quicksort(arr, q + 1, r);	
    }
    

    }

    int findContentChildren(int* g, int gSize, int* s, int sSize) {
    int i, j, maxContChildNum;

    quicksort(g, 0, gSize-1);
    quicksort(s, 0, sSize-1);
    
    maxContChildNum = 0;
    
    for(i = 0, j = 0; i < gSize && j < sSize; j++)
    	if (g[i] <= s[j]){
    		i++;
    		maxContChildNum++;
    	}
    
    return maxContChildNum;	
    

    }


  • 0
    H

    @978333942 直接return i;即可


Log in to reply
 

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