C# Solution - Can you help me clean it up?


  • 0
    J

    The idea is to find the median of one array in the other. Keep doing this until the median index plus its rank in the opposite array is equal to the index of the total median.
    I started with the first array and if not found, did the same for the second. If found in neither then the arrays match and you can return the median of either the first or second array.

       public double FindMedianSortedArrays(int[] nums1, int[] nums2) {
            	
            var lastIndex = nums1.Length + nums2.Length - 1;
    		int loMedIdx, hiMedIdx;
    		loMedIdx = hiMedIdx = lastIndex /2;
    		
    		
    		if (lastIndex % 2 == 1)
    			hiMedIdx++;
    			
    			
    		double t;	
    			
    		if (nums2.Length == 0) {
    			t = nums1[loMedIdx] + nums1[hiMedIdx];
    			return t/2;
    		}
    	
    		if (nums1.Length == 0) {
    			t = nums2[loMedIdx] + nums2[hiMedIdx];
    			return t/2;
    		}
    
    		int lo = 0;
    		int hi = nums1.Length-1;
    		int mid = 0;
    		int r = 0;
    		
     
    		
    		while (lo <= hi)
    		{
    			mid = lo + (hi - lo) /2;
    			r = Rank(nums2, 0, nums2.Length-1, nums1[mid]);
    			int cmp = loMedIdx.CompareTo(mid + r);
    
    			if (cmp < 0)
    				hi = mid-1;
    			else if (cmp > 0)
    				lo = mid+1;
    			else 
    			{
    				if (hiMedIdx > loMedIdx) {
    					if (mid+1 < nums1.Length && r < nums2.Length) {
    						if (nums1[mid+1] < nums2[r])
    						{
    							t = nums1[mid] + nums1[mid+1];
    							return t/2;
    						}
    						else
    						{
    							t = nums1[mid] + nums2[r];
    							return t/2;
    						}
    					}
    					else if (mid+1 < nums1.Length)
    					{
    						t = nums1[mid] + nums1[mid+1];
    						return t/2;
    					}
    					else
    					{
    						t = nums1[mid] + nums2[r];
    						return t/2;
    					}
    				}
    				else
    					return nums1[mid];
    			}
    		}
    		
    		lo = 0;
    		hi = nums2.Length-1;
    		mid = 0;
    		r = 0;
    		
    		while (lo <= hi)
    		{
    			mid = lo + (hi - lo) /2;
    			r = Rank(nums1, 0, nums1.Length-1, nums2[mid]);
    			int cmp = loMedIdx.CompareTo(mid + r);
    
    			
    			if (cmp < 0)
    				hi = mid-1;
    			else if (cmp > 0)
    				lo = mid+1;
    			else
    			{
    				if (hiMedIdx > loMedIdx) {
    					if (mid+1 < nums2.Length && r < nums1.Length) {
    						if (nums2[mid+1] < nums1[r])
    						{
    							t = nums2[mid] + nums2[mid+1];
    							return t/2;
    						}
    						else
    						{
    							t = nums2[mid] + nums1[r];
    							return t/2;
    						}
    					}
    					else if (mid+1 < nums2.Length)
    					{
    						t = nums2[mid] + nums2[mid+1];
    						return t/2;
    					}
    					else
    					{
    						t = nums2[mid] + nums1[r];
    						return t/2;
    					}
    				}
    				else
    					return nums2[mid];
    			}
    			
    		}		
    			
    // still here then arrays must match:
            lastIndex = nums1.Length - 1;
    		loMedIdx = hiMedIdx = lastIndex /2;		
    		
    		if (lastIndex % 2 == 1)
    			hiMedIdx++;
    
    		t = nums1[loMedIdx] + nums1[hiMedIdx];
    		return t/2;
    	}
    	
    	public int Rank(int[] a, int lo, int hi, int goal)
    	{
    		if (hi < lo)
    			return lo;
    		var mid = lo + (hi -lo) /2 ;
    		var cmp = goal.CompareTo(a[mid]);
    		if (cmp < 0)
    			return Rank(a, lo, mid-1, goal);
    		else if (cmp > 0)
    			return Rank(a, mid+1, hi, goal);
    		else 
    			return mid;
    	}
    

Log in to reply
 

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