C Solution, use quick sort O(nlogn)


  • 1
    J
    void swap(int *a, int *b) {
        int temp = *a;
        *a = *b;
        *b = temp;
    }
    int partition(int *nums, int left, int right){
        int x = nums[left]; // pivot
        int record = left;  // record pivot final pos
        for(int i = left + 1; i <= right; i++) {
            if(nums[i] < x){  // move the number which is smaller than pivot to pivot's right side
                record++;
                swap(&nums[i], &nums[record]);
            }
        }
        swap(&nums[record], &nums[left]);  // move pivot to final position
        return record;  // return pivot's index
    }
    
    void quickSort(int *nums, int left, int right){
        if(left >= right) return;
        int pivot = partition(nums, left, right);
        
        quickSort(nums, left, pivot - 1);
        quickSort(nums, pivot + 1, right);
    }
    
    int arrayPairSum(int* nums, int numsSize) {
        quickSort(nums, 0, numsSize - 1);
        int sum = 0;
        for(int i = 0; i < numsSize; i = i + 2) {
            sum = sum + nums[i];
        }
        return sum;
    }
    

Log in to reply
 

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