Accepted C++ O(n) solution via counting_sort


  • 0
    V
    #include <vector>
    #include <algorithm>
    
    using namespace std;
    
    void counting_sort(vector<int>& numbers)
    {
    
        vector<int> p_pos_vec(100000, 0);     // For positive numbers
        vector<int> n_pos_vec(100000, 0);    // For negative numbers
        vector<int> sorted_vec(numbers);
    
        for (vector<int>::iterator iter = numbers.begin(); 
             iter != numbers.end(); ++iter)
        {
            if (*iter >= 0)
                ++p_pos_vec[*iter];
            else 
                ++n_pos_vec[-*iter];
        }
        
        for (vector<int>::iterator _b_iter = n_pos_vec.end() - 2;
             _b_iter >= n_pos_vec.begin(); --_b_iter)
        {   
            *_b_iter += *(_b_iter + 1);
        }
    
        *p_pos_vec.begin() += *n_pos_vec.begin();
    
        for (vector<int>::iterator iter = ++p_pos_vec.begin(); 
             iter != p_pos_vec.end(); ++iter)
        {
            *iter += *(iter - 1);
        }
        
        for (vector<int>::iterator b_iter = --numbers.end();
             b_iter >= numbers.begin(); --b_iter) 
        {
            if (*b_iter >= 0)
                sorted_vec[--p_pos_vec[*b_iter]] = *b_iter; 
            else 
                sorted_vec[--n_pos_vec[-*b_iter]] = *b_iter; 
        }
        
        copy(sorted_vec.begin(), sorted_vec.end(), numbers.begin());
    }
    
    class Solution {
    public:
        vector<int> twoSum(vector<int> &numbers, int target) {
            
            vector<int> result;        
            vector<int> sorted_vec(numbers);
            counting_sort(sorted_vec);
    
            // Give two pointers, one moves forward and another one
            // moves backward
            vector<int>::iterator f_iter = sorted_vec.begin();
            vector<int>::iterator b_iter = --sorted_vec.end();
            
            while (f_iter != b_iter)
            {
                int sum = *f_iter + *b_iter;
                
                if (sum == target)
                {
                    // Find the two values from the vector
                    for (vector<int>::iterator f_i = numbers.begin();
                         f_i != numbers.end(); f_i++) {
                        if (*f_i == *f_iter) {
                            f_iter = f_i;
                            break;
                        }
                    }
    
                    for (vector<int>::iterator b_i = --numbers.end();
                         b_i >= numbers.begin(); b_i--) {
                        if (*b_i == *b_iter) {
                            b_iter = b_i;
                            break;
                        }
                    }
                    
                    result.push_back(min(f_iter, b_iter) - numbers.begin() + 1);
                    result.push_back(max(f_iter, b_iter) - numbers.begin() + 1);
                    return result;
                }
                
                if (sum < target) f_iter++;
                
                if (sum > target) b_iter--;
            }
            
            return result;
        }
    };

  • 0
    S

    Pay attention to "Writing code? Select all code block then click on the {} button to preserve code formatting.” above text editor.


  • 0
    V

    Thanks a lot, this is what I need.


Log in to reply
 

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