[C] A intuitive C solution


  • 0
    P

    Sort the input array in ascending order.
    Then sum the integers which have even id in the sorted series.
    Time complecity: O(nlog(n))

    void mergesort(int* nums, int left, int right, int *swap)
    {
        int mid, lp, rp, sp;
        if (right<=left)
            return;
        mid=(right+left)/2;
        mergesort(nums,left,mid,swap);
        mergesort(nums,mid+1,right,swap);
        
        sp=left;
        lp=left;
        rp=mid+1;
        while(lp<=mid && rp<=right)
            swap[sp++]=nums[lp]<=nums[rp]?nums[lp++]:nums[rp++];
        if(lp<=mid)
            memcpy(&swap[sp],&nums[lp],sizeof(int)*(mid-lp+1));
        if(rp<=right)
            memcpy(&swap[sp],&nums[rp],sizeof(int)*(right-rp+1));
        memcpy(&nums[left],&swap[left],sizeof(int)*(right-left+1));
        return;
    }
    int arrayPairSum(int* nums, int numsSize) {
        int i, sum=0;
        int *swap = (int*)malloc(sizeof(int)*numsSize);
        mergesort(nums,0,numsSize-1,swap);
        for (i=0;i<numsSize;i+=2)
            sum+=nums[i];
        free(swap);
        return sum;
    }
    

Log in to reply
 

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