Mergesort solution in C++


  • 0
    G
    class Solution
    {
    public:
    	struct IndexNumber
    	{
    		int Number;
    		int Index;
    		IndexNumber(int n, int i)
    		{
    			Number = n;
    			Index = i;
    		}
    
    		IndexNumber()
    		{
    			Number = Index = 0;
    		}
    	};
    
    	vector<int> countSmaller(vector<int>& nums)
    	{
    		if (nums.size() == 0) return vector<int>();
    
    		vector<int> state(nums.size(), 0);
    		vector<IndexNumber> numbers;
    		for (int i = 0; i < nums.size(); i++)
    		{
    			IndexNumber in(nums[i], i);
    			numbers.push_back(in);
    		}
    
    		merge(numbers, 0, nums.size() - 1, state);
    
    		return state;
    	}
    
    	void merge(vector<IndexNumber>& nums, int start, int end, vector<int>& state)
    	{
    		if (start == end)
    		{
    			return;
    		}
    
    		int mid = (start + end) / 2;
    		merge(nums, start, mid, state);
    		merge(nums, mid + 1, end, state);
    
    		vector<IndexNumber> ret(end - start + 1, IndexNumber());
    		int p0 = 0;
    		int p1 = start;
    		int p2 = mid+1;
    
    		while (p0 < ret.size())
    		{
    			while (p1 <=mid && p2<=end && nums[p1].Number <= nums[p2].Number)
    			{
    				ret[p0++] = nums[p1++];
    			}
    
    			int count = 0;
    			while (p1 <=mid && p2<=end && nums[p1].Number>nums[p2].Number)
    			{
    				count++;
    				ret[p0++] = nums[p2++];
    			}
    
    			for (int t = p1; t <=mid; t++)
    			{
    				state[nums[t].Index] += count;
    			}
    
    			if (p1 == mid+1)
    			{
    				for (int t = p2; t <=end; t++)
    				{
    					ret[p0++] = nums[t];
    				}
    			}
    
    			if (p2 == end+1)
    			{
    				for (int t = p1; t <=mid; t++)
    				{
    					ret[p0++] = nums[t];
    				}
    			}
    		}
    
    		for (int i = 0; i < ret.size(); i++)
    		{
    			nums[start + i] = ret[i];
    		}
    	}
    };

Log in to reply
 

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