Reimplement the top-voted java code in C (6ms)


  • 0
    D

    Please read the original post and their discussions here.

    The idea is quite simple but the coding part is kind of complicated when you use C because you need to write sort and dynamic array by hand, which is the major purpose of this post.

    /* Here we implement the quick sort algorithm. */
    void swap(int *a, int *b) {
        int temp = *a;
        *a = *b;
        *b = temp;
    }
    int partition(int *arr, int left, int right) {
        int pi = left;
        for (int i = left; i < right; ++i) {
            if (arr[i] <= arr[right])
                swap(&arr[pi++], &arr[i]);
        }
        swap(&arr[pi], &arr[right]);
        return pi;
    }
    void quick_sort(int *arr, int left, int right) {
        if (left >= right) return;
        int pi = partition(arr, left, right);
        quick_sort(arr, left, pi-1);
        quick_sort(arr, pi+1, right);
    }
    
    /* Here we implement the logic to double size a 2-D array. */
    void check_size(int ***rets_ref, int *curr_size, int *max_size) {
        // we need to pass 2-D array as (int ***) to modify in place.
        if (*curr_size < *max_size) return;
        *max_size *= 2; // double size
        int **rets = malloc(sizeof(int *)*(*max_size));
        for (int i = 0; i < *curr_size; ++i) {
            rets[i] = (*rets_ref)[i];
        }
        int **tmp = *rets_ref; 
        *rets_ref = rets; 
        free(tmp);
    }
    
    /* Here we implement the 2-sum, 3-sum and 4-sum logic. */
    void twoSum(int *nums, int numsSize, int target, int pi, int ***rets_ref, int *returnSize, int *size, int z1, int z2) {
        int **rets;
        int i = pi, j = numsSize-1, sum, x;
        while (i < j) {
            sum = nums[i] + nums[j];
            if (sum == target) {
                rets = *rets_ref; // may be resized during iteration
                rets[*returnSize] = malloc(sizeof(int)*4);
                rets[*returnSize][0] = z1;
                rets[*returnSize][1] = z2;
                rets[*returnSize][2] = nums[i];
                rets[*returnSize][3] = nums[j];
                (*returnSize)++;
                check_size(rets_ref, returnSize, size); // check and resize
                x = nums[i];
                while(++i < j && x == nums[i]); //avoid duplicate
                x = nums[j];
                while(--j > i && x == nums[j]); //avoid duplicate
            } else if (sum < target) {
                i++;
            } else {
                j--;
            }
        }
    }
    void threeSum(int *nums, int numsSize, int target, int pi, int ***rets_ref, int *returnSize, int *size, int z1) {
        int **rets;
        for (int i = pi; i < numsSize; ++i) {
            if (i >= numsSize-2)
                break; //no more
            if (i > pi && nums[i] == nums[i-1])
                continue; //avoid duplicate
            if (nums[i]+2*nums[numsSize-1] < target)
                continue; //too small
            if (3*nums[i] > target)
                break; //to large
            if (3*nums[i] == target) {
                rets = *rets_ref;
                if (i+2 < numsSize && nums[i+2] == nums[i]) {
                    rets[*returnSize] = malloc(sizeof(int)*4);
                    rets[*returnSize][0] = z1;
                    for (int j = 0; j < 3; ++j)
                        rets[*returnSize][j+1] = nums[i+j];
                    (*returnSize)++;
                    check_size(rets_ref, returnSize, size); // check and resize
                }
                break;
            }
            twoSum(nums, numsSize, target-nums[i], i+1, rets_ref, returnSize, size, z1, nums[i]);
        }
    }
    int** fourSum(int *nums, int numsSize, int target, int *returnSize) {
        int **rets;
        int size = numsSize;
        rets = malloc(sizeof(int *)*size);
        *returnSize = 0;
        quick_sort(nums, 0, numsSize-1);
        for (int i = 0; i < numsSize; ++i) {
            if (i >= numsSize-3)
                break; //no more
            if (i && nums[i] == nums[i-1]) 
                continue; //skip duplicate
            if (nums[i]+3*nums[numsSize-1] < target) 
                continue; //too small
            if (4*nums[i] > target)
                break; //to large
            if (4*nums[i] == target) {
                if (i+3 < numsSize && nums[i+3] == nums[i]) {
                    rets[*returnSize] = malloc(sizeof(int)*4);
                    for (int j = 0; j < 4; ++j)
                        rets[*returnSize][j] = nums[i+j];
                    (*returnSize)++;
                    check_size(&rets, returnSize, &size); // check and resize
                }
                break;
            }
            threeSum(nums, numsSize, target-nums[i], i+1, &rets, returnSize, &size, nums[i]);
        }
        return rets;
    }
    

    It will be more elegant to implement a dynamic array and some methods.


Log in to reply
 

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