92ms C++ quick-sort & binary-search & enum


  • -1
    M

    // 92ms C++
    // quick-sort & binary-search & enum

    // search a sol within the range: [is, js], which satisfied
    // 1: is + it + js == 0
    // 2: is != it;
    // 3: js != it

    class Solution {
    using _iter_t = std::vector<int>::iterator;
    using _size_t = std::vector<int>::size_type;

    public:
    std::vector<std::vector<int>> threeSum(std::vector<int> &seq)
    {
    // at least 3 elems
    if (seq.size() >= 3) {
    quick_sort(seq.begin(), seq.end());
    do_solve(seq);
    }

    	return std::move(result);
    }
    

    private:
    void do_solve(std::vector<int> &seq)
    {
    // [@ss, @se]
    const auto ss = seq.begin();
    const auto se = seq.begin() + seq.size() - 1;

    	for (auto is = ss, ie = se - 1; is != ie; ++is) {
    		if (is != ss && *is == *(is - 1)) {
    			continue;
    		}
    
    		for (auto js = se, je = is + 1; js != je; --js) {
    			 if (js != se && *js == *(js + 1)) {
    			 	continue;
    			 }
    
    			// do search on (@is, @js)
    			auto trg = -(*is + *js);
    			auto it  = binary_search(is, js, trg);
    
    			if (it != js && it != is) {
    				res.insert(std::make_tuple(*is, *it, *js));	
    			}
    		}
    	}
    
    	for (const auto &r : res) {
    		result.push_back({std::get<0>(r), std::get<1>(r), std::get<2>(r)});
    	}
    }
    
    // binary search on [@beg, @end)
    _iter_t binary_search(_iter_t beg, _iter_t end, int trg)
    {
    	for (_iter_t s = beg, e = end; s != e;) {
    		_iter_t m = s + (e - s) / 2;
    		if (*m == trg) {
    			return m;
    		} 
    
    		if (*m < trg) {
    			s = m + 1;
    		} else {
    			e = m;
    		}
    	}
    
    	return end;
    }
    
    // Quick Sort on [@beg, @end)
    void quick_sort(_iter_t beg, _iter_t end)
    {
    	if (end - beg >= 2) {
    		auto prt = partition(beg, end);
    		quick_sort(beg, prt);
    		quick_sort(prt + 1, end);
    	}
    }
    
    // Partition on [@beg, @end)
    _iter_t partition(_iter_t beg, _iter_t end)
    {
    	_size_t nr = end - beg - 1;	
    
    	std::default_random_engine re(std::labs(*beg));
    	// default template argument 
    	std::uniform_int_distribution<> dis(0, nr); // [0, nr]
    
    	_size_t id = dis(re);
    
    	swap(beg + id, beg + nr);
    
    	_iter_t i = end;
    	_iter_t j = beg;
    	while (j < beg + nr) {
    		if (*j < *(beg + nr)) {
    			i = i == end ? beg : i + 1;
    			swap(i, j);
    		}
    		++j;
    	}
    
    	i = i == end ? beg : i + 1; // be-careful
    	swap(i, beg + nr);
    
    	return i;
    } 
    
    void swap(_iter_t a, _iter_t b) 
    {
    	if (a != b) {
    		// C++ Primer P135/136
    		// use decltype() is a error, because decltype(*a) is a ref
    		// decltype(*a) m = *a;
    		auto m = *a;
    		*a = *b;
    		*b = m;
    	}
    }
    

    private:
    std::set<std::tuple<int, int, int>> res;
    std::vector<std::vector<int>> result;
    };


Log in to reply
 

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