Leetcode/561Array_Partition at main · yayajjiang/Leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
public:
    void quicksort(vector<int>& nums, int i, int j){
        if(i >= j)  return;
        int k = nums[(i+j)/2]; int l = i - 1; int r = j + 1;

        while( l < r){
            do{(l++);} while (nums[l] < k);
            do{(r--);} while (nums[r] > k);
            if( l < r)  swap(nums[l], nums[r]);
        }
        quicksort(nums, i, r);
        quicksort(nums,r+1, j);


    }
    int arrayPairSum(vector<int>& nums) {
        int max = 0;
        int i = 0; int j = nums.size()-1;
        quicksort(nums, i, j);
        for(int k = 0; k < nums.size(); k++){
            if(k%2==0){
                max += nums[k];
            }
        }
        return max;
    }
};


class Solution {
public:
       int arrayPairSum(vector<int>& nums) {
           sort(nums.begin(),nums.end());
           int sum = 0;
           for(int i =0;i<nums.size();i+=2)
               sum+=nums[i];
           return sum;
    }
};