C++ O(n), counting sort


  • 0
    W
    int arrayPairSum(vector<int>& nums) {
        int a[20001] = {0};
        for(auto i: nums)
            a[i+10000]++;
        int sum = 0, rest = 1;    
        for(int i = 0; i <= 20000; i++){
            if(a[i]){
                sum += (a[i]+rest) / 2 * (i-10000);
                rest = (a[i]+rest) % 2;
            }
        }
        return sum;
    }

Log in to reply
 

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