Heap solution with clean code


  • 0
    S
    double findMedianSortedArrays(int A[], int m, int B[], int n)
    {
    	int total = m + n;
    	int k1 = -1, k2 = -1;
    	
    	if (total % 2)
    	{
    		k1 = (m + n + 1) >> 1;
    		k2 = k1;
    	}
    	else
    	{
    		k1 = (m + n) >> 1;
    		k2 = k1 + 1;
    	}
    	vector<int> vec(total - k2, 0);
    	vector<int> veck(k2, 0);
    	for (int i = 0; i < total; i++)
    	{
    		if (i < k2)
    		{
    			if (i < m)
    				veck[i] = A[i];
    			else
    				veck[i] = B[i - m];
    		}
    		else
    		{
    			if (i < m)
    				vec[i-k2] = A[i];
    			else
    				vec[i-k2] = B[i - m];
    		}	
    	}
    	
    	std::make_heap(veck.begin(), veck.end());//default max heap
    	for (int j = 0; j < vec.size(); ++j)
    	{
    		int heapmax = veck.front();
    		if (vec[j] < heapmax)
    		{
    			std::pop_heap(veck.begin(), veck.end());
    			veck.pop_back();
    			veck.push_back(vec[j]);
    			std::push_heap(veck.begin(), veck.end());
    		}
    	}
    
    	if (k1 == k2)
    	{
    		return veck.front();
    	}
    	else
    	{
    		int heapmax1 = veck.front();
    		pop_heap(veck.begin(), veck.end());
    		veck.pop_back();
    		std::push_heap(veck.begin(), veck.end());
    		int heapmax2 = veck.front();
    		return (float)(heapmax1 + heapmax2) / 2.0;
    	}
    }

Log in to reply
 

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