Why 68ms vs 20ms


  • 0
    C

    Here are two different method I used to solve the problem. However, The first one with a "helper" function is 68ms, the second with only one method is 20ms.

    I can not find a reasonable answer to explain this , Please help!

    First one(68ms)

    class Solution {
    public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
    
    	if (nums.size() <= 0)
    		return NULL;
    	if (nums.size() == 1)
    	{
    		return new TreeNode(nums[0]);
    	}
    	int n = nums.size();
    	
    	return helper(0, n - 1, nums);
    }
    TreeNode* helper(int s, int e, vector<int> nums)
    {
    	if (s > e)
    		return NULL;
    	if (s == e)
    		return new TreeNode(nums[s]);
    	int mid =  s + (e - s) / 2;
    	TreeNode* root = new TreeNode(nums[mid]);
    	root->left = helper(s, mid - 1, nums);
    	root->right = helper(mid + 1, e,  nums);
    	return root;
    }
    };
    

    Second one(20ms):

    class Solution {
    public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
    
    	if (nums.size() <= 0)
    		return NULL;
    	if (nums.size() == 1)
    	{
    		return new TreeNode(nums[0]);
    	}
    	int n = nums.size();
    	int mid = n / 2;
    	TreeNode* root = new TreeNode(nums[mid]);
    
    	vector<int> leftInts(nums.begin(), nums.begin() + mid);
    	vector<int> rightInts(nums.begin()+mid+1, nums.end());
    	root->left = sortedArrayToBST(leftInts);
    	root->right = sortedArrayToBST(rightInts);
    
    	return root;
    }
    
    };

  • 0
    S

    Your helper parameter: vector<int> nums is not a reference type! That means, for each recursive call, THE ENTIRE input array is copied over and over again.

    Make this parameter, const vector<int> &nums (the const is optional), and you'll see the helper solution run faster!


Log in to reply
 

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