[LeetCode] 4. Median of Two Sorted Arrays

[grandyang]

[LeetCode] 4. Median of Two Sorted Arrays

[lld2006]

 解法3 虽然好， 但是不容易理解。 论坛高票解法相对来说更容易理解。
高票解法是在较短的数组中选择一个分割。 其实是等价于解法3的。
class Solution {
public:
double findMedianSortedArrays(vector& nums1, vector& nums2) {
if(nums2.size() < nums1.size()) return findMedianSortedArrays(nums2, nums1);
int left1 = 0, right1 = nums1.size();
int half = (nums1.size()+nums2.size()+1)/2; //left median or median
int max_left=0, min_right=0;
while(left1<= right1){
int mid1 = (left1+right1)/2;
int mid2 = half-mid1;
if(mid1 < nums1.size() && nums1[mid1] < nums2[mid2-1]){
left1 = mid1+1;
}else if(mid1 > 0 && nums1[mid1-1] > nums2[mid2]){
right1 = mid1-1;
}else{
if(mid1 == 0)
max_left = nums2[mid2-1];
else if(mid2 == 0)
max_left = nums1[mid1-1];
else
max_left = max(nums1[mid1-1], nums2[mid2-1]);
if((nums1.size()+ nums2.size()) & 1) return max_left;
if(mid1 == nums1.size())
min_right = nums2[mid2];
else if(mid2 == nums2.size())
min_right = nums1[mid1];
else{
min_right = min(nums1[mid1], nums2[mid2]);
}
return (static_cast(min_right) + max_left)/2;
}
}
assert(0);
return -1;
}
};

[bluce-ben]

Go语言解法，思路比较简单，就是写的算法有点长，不过比较好理解。没有优化过，第一版本的，跟着思路写的。leetcode已经通过的，所以算法是正确的，可以放心看

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
    var sum int
	lengthSum := len(nums1) + len(nums2)
	// 算法**，去除不符合的数值，最后剩下的就是结果。或为2个，或为1个
	nums := lengthSum / 2
	if lengthSum % 2 == 0 {
		nums--
	}
	for i := 0; i < nums; i++ {
		//删除不符合的数值，每次删除一个最大值、一个最小值
		var (
			minNum1 int
			minNum2 int
			maxNum1 int
			maxNum2 int
		)

		if len(nums1) > 0 {
			minNum1 = nums1[0]
			maxNum1 = nums1[len(nums1)-1]
		}
		if len(nums2) > 0 {
			minNum2 = nums2[0]
			maxNum2 = nums2[len(nums2)-1]
		}
		// 确保必须要删除最小值
		if minNum1 > minNum2 {
			if len(nums2) != 0 {
				nums2 = nums2[1:]
			} else if len(nums1) != 0 {
				nums1 = nums1[1:]
			}
		} else if minNum1 <= minNum2 {
			if len(nums1) != 0 {
				nums1 = nums1[1:]
			} else if len(nums2) != 0 {
				nums2 = nums2[1:]
			}
		}

		// 确保必须删除最大值
		if maxNum1 > maxNum2 {
			if len(nums1) != 0 {
				nums1 = nums1[:len(nums1)-1]
			} else if len(nums2) != 0 {
				nums2 = nums2[:len(nums2)-1]
			}
		} else if maxNum1 <= maxNum2 {
			if len(nums2) != 0 {
				nums2 = nums2[:len(nums2)-1]
			} else if len(nums1) != 0 {
				nums1 = nums1[:len(nums1)-1]
			}
		}
	}
	var count int
	if len(nums1) > 0 {
		for _, v := range nums1 {
			sum += v
			count++
		}
	}
	if len(nums2) > 0 {
		for _, v := range nums2 {
			sum += v
			count++
		}
	}

	var res float64
	if count == 1 {
		res = float64(sum)
	} else {
		res = float64(sum)/2.0
	}

	return res
}

[Alpensin]

Python

class Solution:
    def find_k(self, arr1, i, arr2, j, k):
        if i >= len(arr1):
            return arr2[j + k - 1]
        if j >= len(arr2):
            return arr1[i + k - 1]
        if k == 1:
            return min(arr1[i], arr2[j])
        if i + k // 2 - 1 < len(arr1):
            midVal1 = arr1[i + k // 2 - 1]
        else:
            midVal1 = float("+inf")
        if j + k // 2 - 1 < len(arr2):
            midVal2 = arr2[j + k // 2 - 1]
        else:
            midVal2 = float("+inf")
        if midVal1 < midVal2:
            return self.find_k(arr1, i + k // 2, arr2, j, k - k // 2)
        else:
            return self.find_k(arr1, i, arr2, j + k // 2, k - k // 2)
    
    def findMedianSortedArrays(self, arr1: List[int], arr2: List[int]) -> float:
        m = len(arr1)
        n = len(arr2)
        left = (m + n + 1) // 2
        right = (m + n + 2) // 2
        return (self.find_k(arr1, 0, arr2, 0, left) + self.find_k(arr1, 0, arr2, 0, right)) / 2