C++ implement 59ms Accepted


  • 0
    F

    How does the fastest c++ algorithm implement?
    alt text


  • 0
    F
    int Solution::findCountentChildren(vector<int>& g, vector<int>& s)
    {
    	sort(g.begin(), g.end());
    	sort(s.begin(), s.end());
    	int i = 0, j = 0;
    	while (i<g.size() && j<s.size())
    	{
    		if (g[i] <= s[j])
    		{
    			i++;
    		}
    		j++;
    	}
    	return i;
    }
    

  • 1
    F

    this is 59ms, last is 93ms

    class Solution {
    public:
        int findContentChildren(vector<int>& g, vector<int>& s) {
    	sort(&g[0], &g[0]+g.size());
    	sort(&s[0], &s[0]+s.size());
    	int i = 0, j = 0;
    	while (i<g.size() && j<s.size())
    	{
    		if (g[i] <= s[j])
    		{
    			i++;
    		}
    		j++;
    	}
    	return i;
        }
    };
    

  • 0
    B

    @fanbinjim Could you explain why the second STL sorting call is significantly faster?


  • 0
    V

    @fanbinjim Might optimize this code by assigning local variables int m = g.size(), n = s.size(); and use m and n in sort and while conditions. I achieved 56ms with

    class Solution {
    public:
        int findContentChildren(vector<int>& g, vector<int>& s) {
            int i = 0, j = 0, m = g.size(), n = s.size();
            sort(&g[0], &g[0]+m);
            sort(&s[0], &s[0]+n);
            while (i < m && j < n) {
                if (s[j] >= g[i])
                    i++;
                j++;
            }
            return i;
        }
    };
    
    

Log in to reply
 

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