c greedy solution with quick sort algorithm


  • 0
    int partition(int* a, int l, int r) {
        int x = a[l];
        while(l < r) {
            while(l < r && a[r] >= x) --r;
            if(l < r) {
                a[l] = a[r];
                ++l;
            }
            while(l < r && a[l] < x) ++l;
            if(l < r) {
                a[r] = a[l];
                --r;
            }
        }
        a[l] = x;
        return l;
    }
    
    void quick_sort(int* a, int l, int r) {
        if(l < r) {
            int q = partition(a, l, r);
            quick_sort(a, l, q-1);
            quick_sort(a, q+1, r);
        }
    }
    
    int findContentChildren(int* g, int gSize, int* s, int sSize) {
        quick_sort(g, 0, gSize-1);
        quick_sort(s, 0, sSize-1);
        int n = 0, i = 0, j = 0; // n is content number
        while(i < gSize && j < sSize) {
            if(g[i] <= s[j]) {
                ++i;
                ++j;
                ++n;
            } else {
                ++j;
            }
        }
        return n;
    }
    

Log in to reply
 

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