c++ code O(n),beats 100%


  • 23
    D
    class Solution {
    public:
        int arrayPairSum(vector<int>& nums) {
            vector<int> hashtable(20001,0);
            for(size_t i=0;i<nums.size();i++)
            {
                hashtable[nums[i]+10000]++;
            }
            int ret=0;
            int flag=0;
            for(size_t i=0;i<20001;){
                if((hashtable[i]>0)&&(flag==0)){
                    ret=ret+i-10000;
                    flag=1;
                    hashtable[i]--;
                }else if((hashtable[i]>0)&&(flag==1)){
                    hashtable[i]--;
                    flag=0;
                }else i++;
            }
            return ret;
        }
    };
    

    with the range of numbers,it is easy to using vector,and if we don't know the range of numbers,maybe using STL multiset,but using multiset is O(nlogn).


  • 7

    a little bit of improvement...

    class Solution {
    public:
        int arrayPairSum(vector<int>& nums) {
            int ret = 0;
            bool flag = true;
            array<int, 20001> hashtable{ 0 };
            for (const auto n : nums) {
                ++hashtable[n + 10000];
            }
            for (int i = 0; i < 20001;) {
                if (hashtable[i] > 0) {
                    if (flag) {
                        flag = false;
                        ret += (i - 10000);
                        --hashtable[i];
                    } else  {
                        flag = true;
                        --hashtable[i];
                    }
                } else
                    ++i;
            }
            return ret;
        }
    };
    

  • 1
    D

    @i_square it is a good habit to use bool flag,ty


  • 0
    M

    nice solution


  • 2
    M

    Thank you,I use sort originally. Your thinking make it quicker.

    class Solution {
    public:
        int arrayPairSum(vector<int>& nums) {
            vector<short> hash(20001);
            int sum=0;
            for (auto e:nums) {++hash[e+10000];}
            for (int i=0,j=1; i<20001; ) {
                if (hash[i]>0) {
                    if (j==1) {sum+=i-10000;}
                    j^=1;
                    if (--hash[i]==0) ++i;
                } else {++i;}
            }
            return sum;
        }
    };
    

  • 4
    B

    a little improvement

    int arrayPairSum(vector<int>& nums) {
        vector<int> map(20001,0);
        for(auto n:nums)map[n+10000]++;
        int result=0,remain=0;
        for(int x=0;x<=20000;x++)
        {
            
            result+=(x-10000)*((map[x]+1-remain)/2);
            remain=(remain+map[x])%2;
        }
        
        return result;
    }

  • 3
    J

    Could someone explain what the code is doing? I'm having a hard time following this one.


  • 6
    M

    @jejeirs Bucket sort,you can google it.


  • 3

    @jejeirs Idea: Bucket Sort can sort an integer array in linear time when we know the scope of all the integers.


  • 0
    N

    is this hashtable an unordered_map?


  • 0

    @needforspeed vector<int> hashtable(20001,0); I think it is a vector of int.


  • 0
    G

    good job.
    as a newbie,I have learned a lot from bool true


  • 6
    M

    Keep counting so that you do not need to loop to the end of the buckets if not necessary

    class Solution {
    public:
        int arrayPairSum(vector<int>& nums) {
            // Using bucket sort since we know the range of the integers are from -10000 - 10000
            
            vector<int> buckets(200001, 0);
            for(int i:nums) {++buckets[i+10000];}
            
            int sum = 0, count = 0, i = 0;
            while(count < nums.size()) {
                if(buckets[i]==0) {
                    i++;
                }
                else {
                    if(count%2==0) 
                        sum += (i-10000);
                    --buckets[i];
                    ++count;
                }
            }
            return sum;
        }
    };
    

  • 0
    N

    @morrischen2008 That's a nice addition to the solution! thanks.


  • 0
    L

    Nice solution. Here's a C version:

    int arrayPairSum(int* nums, int numsSize) {
        bool flag = true;
        int ret = 0;
        int hashtable[20001] = {0};
        for (int i = 0; i < numsSize; i++) {
            hashtable[nums[i] + 10000]++;
        }
        for (int i = 0, count = 0; i < 20001, count < numsSize / 2; ) {
            if (hashtable[i] > 0) {
                if (flag) {
                    ret += i - 10000;
                    count++;
                }
                flag = !flag;
                if (--hashtable[i] == 0) {
                    i++;
                }
            } else {
                i++;
            }
        }
        return ret;
    }
    

  • 0
    B

    @lun0522 said in c++ code O(n),beats 100%:

    nums

    Could you please give me the details of the algorithm? I solved in nlogn time but this one looks like more efficient. Thank you very much


  • 10
    L

    @bernakabadayi Sure.

    To make it easier to understand, suppose that all the integers in the array will be in the range of [0, 10000] rather than [-10000, 10000]. We create an array, named hashtable, whose capacity should be (10000 - 0) + 1 = 10001. This array is used to keep track of the times that an element appears in the original array.

    The key is to use the element itself as the index. For example, we traverse nums, if we encounter a 5, just do hashtable[5]++;; if we encounter a '9', do hashtable[9]++;, and so on. This is what the first for loop used to do.

    In the second loop, we traverse hashtable. If hashtable[0] == 2, which means there are two 0 in nums, so the sorted array should start with two 0; if hashtable[1] == 3, there should be three 1 after those two 0, etc.

    Here we set two variables, flag and count. Since we just have to calculate the sum of min(ai, bi), which is the same to the sum of elements in even-index positions (0, 2, 4, ...) in the sorted array. flag labels whether the element is in an even or odd position, and count is a sentinel that stops the loop.

    Each time we encounter an element, do --hashtable[i] to record we have already dealt with it. But i should not increase by 1 every time. Say if we have hashtable[5] == 2, after we dealt with the first 5, i should keep being 5 so we will encounter the second 5 later. That's why we use:

    if (--hashtable[i] == 0) {
        i++;
    }
    

    In the problem, the range of elements is [-10000, 10000], so we have to create an hashtable of length 10000 - (-10000) + 1 = 20001; in the first loop, use hashtable[nums[i] + 10000]++; instead so that indices would not be negative; in the second loop, use ret += i - 10000; to neutralize that 10000 added before.

    I think this is clear enough. The time complexity should be O(n). This method is especially useful if we know the range of elements, and the range is not very large (like [INT_MIN, INT_MAX]) (or the space complexity will be huge).

    Happy coding!


  • 0
    P

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

    }
    

    };
    //how about this?


  • 1
    A

    a little bit improvement...

        int arrayPairSum(vector<int>& nums) {
            int res = 0;
            vector<int> bucket(20001, 0);
            int mini = 10000, maxi = -10000;
            for (int i = 0; i < nums.size(); ++i) {
                bucket[nums[i] + 10000]++;
                mini = min(mini, nums[i]);
                maxi = max(maxi, nums[i]);
            }
            bool odd = false;
            for (int i = mini+10000; i <= maxi+10000; ++i) {
                res += (i - 10000) * (bucket[i] / 2);
                if (!odd && (bucket[i] % 2 == 1)) res += i - 10000;
                odd ^= (bucket[i] % 2 == 1);
            }
            return res;
        }
    

  • 0
    I

    @morrischen2008 nice implementation, easier to read and understand ! COOL


Log in to reply
 

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