logo标签列表

两个不同长度有序数组的中位数

algorithm
3
我正在尝试理解这个算法，它可以在O(log(n+m))的时间复杂度内解决这个问题，其中n和m是数组的长度。我已经发布了该算法的解释链接：https://www.geeksforgeeks.org/median-of-two-sorted-arrays-of-different-sizes/ 对于我来说，完全消化这个算法的思想非常困难。我可以看出，这个算法的思想是将一个数组的长度减少到1或2，然后应用基本情况。基本情况是有意义的，但我想知道是否可以省略n = 2的基本情况，只处理n = 1。我也不理解剩余部分的内容。对我来说，看起来很奇怪，我们必须从开始到idx截取数组B[]。这很奇怪，因为idx可能等于B[]的长度，所以我们会忽略整个数组。
你了解二分查找的工作原理吗？ - mariusz_latarnik01
是的，二分查找是通过将数据集减半来寻找某个元素的技巧。 - patzi
1
所以我们有数组a =“aaaaaaaaaa”和数组b =“bbbbbbbbbbbbbbbbbbb”，如果我们合并它们并排序，它会变成“abababbabababbbbababaaba”的样子，我们的目标是在每一步中获取数组的最中间部分，因此“ababab [babababbbbab] abaaba” < - [这部分]是最中间的。现在我们想要不合并就做到这一点，因为合并是O（n），而我们可以在O（logn）中完成它。在每个步骤中，我们希望丢弃一半的元素，并获得中间部分。我们正在寻找数组的中间部分：1“aaaaa || aaaaa”2，1“bbbbbbbbb || bbbbbbbbbb”2，然后我们思考： - mariusz_latarnik01
我们想要a1和a2，a1和b1，a1和b2，a2和b1，a2和b2，或者b1和b2吗？所以我们有6种取一半元素的可能性，我们通过比较中间元素来决定，其中我们所有的中间元素肯定都在。 - mariusz_latarnik01
@ottomeister 等于 != 不同 - patzi
显示剩余3条评论
8个回答
7
TL;DR:
主要思想是，如果您从数字集中删除了N个明显小于（或等于）中位数的元素，并且删除了相同数量的明显大于或等于中位数的元素，则可以这样做。
让我们用一个例子来解释一下：
A = [1 2 3 9 10]，B = [3 4 5 6 7 8 9]
标记为中间元素：
A = [1 2 3 9 10]，B = [3 4 5 6 7 8 9]
总体中位数将在3和6之间（含）。因此，如果我们删除小于3的两个元素和大于6的两个元素，我们仍然会得到相同的中位数。我们从A中删除较小的元素，在B中删除较大的元素：
A = [39 10]，B = [3 4 5 6 7]
现在我们从A中删除一个大于9的元素，从B中删除一个小于5的元素：
A = [3 9]，B = [4 5 6 7]
我们到达Case 4（较小的数组有2个元素）：算法要求中位数为
B[M / 2]，B[M / 2–1]，max（A[0]，B[M / 2–2]），min（A[1]，B[M / 2+ 1]）
即B [2]，B [1]，max（A [0]，B [0]），min（A [1]，B [3]）
即6,5，max（3,4），min（9,7）
即[6 5 4 7]
该数组的中位数为5.5。这就是正确的结果。
我们能否继续减少数据集，直到其中一个数组的大小为1？A = [3]，B = [5 6 7] - patzi
@Dan 你说得对，没有必要用一个两个元素的数组来停止算法。由于B中位数为5.5，A中位数为6，因此可以完全删除A中的9和B中的4。最后，您可以从A中删除3和从B中删除7，使A为空，并从B中取中位数为[5 6]。 - Ralf Kleberhoff
如果我们按照您所说的将A清空并将B减少到2，那么时间复杂度将是O(log(max(m,n)))而不是O(log(min(m,n)))，@RalfKleberhoff。 - Yusuf
0
class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        nums1.extend(nums2)
        newArray = sorted(nums1)
        
        if len(newArray)%2==0:
            index = len(newArray)//2
            median = (newArray[index] + newArray[index-1])/2
            return float(median)
        else:
            index = len(newArray)//2
            median = newArray[index]
            return float(median)


if __name__ == '__main__':
    obj = Solution()
    print(obj.findMedianSortedArrays([1,3],[2]))
0

两个已排序数组的中位数 | 相同长度 | 不同长度

首先，我们需要将两个数组按照排序顺序合并。然后，我们可以找到中位数。中位数将是排序数组的中心元素。

 var findMedianSortedArrays = function(nums1, nums2) {
  let array = [], leftIndex = 0, rightIndex = 0;
  while (leftIndex < nums1.length && rightIndex < nums2.length) {
    if (nums1[leftIndex] < nums2[rightIndex]) {
      array.push(nums1[leftIndex]);
      leftIndex++;
    } else {
      array.push(nums2[rightIndex]);
      rightIndex++;
    }
  }

  // add uninitiated remaining element from either array if any remains. 
  array = array.concat(nums1.slice(leftIndex)).concat(nums2.slice(rightIndex));

  if (array.length % 2 == 0) {
    return (array[(array.length / 2) - 1] + array[array.length / 2]) / 2;
  } else {
    return array[Math.floor(array.length / 2)]
  }
};
findMedianSortedArrays([1 2 3 9 10], [3 4 5 6 7 8 9]);
0
    class Solution(object):
      def findMedianSortedArrays(self, nums1, nums2):
      merged_array = (nums1 + nums2)
      merged_array.sort()
      l_m_a = len(merged_array)
      count = int(l_m_a / 2)

      if l_m_a % 2 == 1:
        median = merged_array[count]
        return median
      else:
        median_in_even = (merged_array[count] + merged_array[count - 1]) / 2
        return median_in_even
0

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function (nums1, nums2) {
    let newArray = [];
    let median;

    if (nums1.length > 0 && nums2.length > 0) {
        newArray = [...nums1, ...nums2]
        newArray.sort(function (a, b) {
            return a - b;
        })
    } else if (nums1.length === 0) {
        newArray = nums2
        newArray.sort(function (a, b) {
            return a - b;
        })
    } else if (nums2.length === 0) {
        newArray = nums1
        newArray.sort(function (a, b) {
            return a - b;
        })
    }
    if (newArray.length === 1) {
        return newArray[0]
    }
    if (newArray.length === 3) {
        return newArray[1]
    }

    if (newArray.length % 2 === 0) {
        const findIndex = Math.floor(newArray.length / 2)
        console.log("findIndexeven", findIndex)
        const addValue = Math.max((newArray[findIndex - 1] + 
          newArray[findIndex]), 0)
        median = addValue / 2
    } else {
        const findIndex = Math.floor(newArray.length / 2) + 1
        console.log("findIndexodd", findIndex)
        median = newArray[findIndex - 1]
    }
    console.log("medianValue",median)
    return median
  };

  findMedianSortedArrays([1, 2], [3, 4])

0
def findmedian(A,B):
    if len(A) > len(B):
        return findmedian(B,A)# always ensuring that we do the binsearch on the shorter arr
    x = len(A)
    y = len(B)
    start = 0# start and end of shorter arr
    end = x
    while (start <= end):
        partition_x = (start + end)//2# the mid of smaller arr, partition_x is an index
        partition_y = (x+y+1)//2 - partition_x# the suitable partition of larger arr to divide the arrs into equal halves
        if partition_x == 0:# if there is nothing on the left
            left_x = None
        if partition_x == x:# if there is nothing on the right
            right_x = sys.maxint# +inf
        if partition_y == 0:
            left_y = None# this is -inf similar to the case for smaller arr
        if partition_y == y:
            right_y = sys.maxint

        if (left_x <= right_y) and (left_y <= right_x):# all the elems on left are smaller than all the elems on right is ensured by
         #checking on the extremes only since arrs sorted. Also, the partition always makes equal halves, so found the right spot.
            if (x+y) % 2 == 0:
                return (max(left_x,left_y) + min(right_x,right_y))/2.0
            else:
                return max(left_x,left_y)# if the num of elems is odd
            elif left_x > right_y:# if we have come more towards right of smaller arr, then move left on smaller arr
                end = partition_x -1
            else:# if we have come more to the left
                start = partition_x + 1
0
class Solution {

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;

// Make sure nums1 is the smaller array
if (m > n) {
    int[] temp = nums1;
    nums1 = nums2;
    nums2 = temp;
    int tmp = m;
    m = n;
    n = tmp;
}

int iMin = 0, iMax = m, halfLen = (m + n + 1) / 2;
while (iMin <= iMax) {
    int i = (iMin + iMax) / 2;
    int j = halfLen - i;
    if (i < iMax && nums2[j-1] > nums1[i]){
        iMin = i + 1; // i is too small
    }
    else if (i > iMin && nums1[i-1] > nums2[j]) {
        iMax = i - 1; // i is too big
    }
    else { // i is perfect
        int maxLeft = 0;
        if (i == 0) { maxLeft = nums2[j-1]; }
        else if (j == 0) { maxLeft = nums1[i-1]; }
        else { maxLeft = Math.max(nums1[i-1], nums2[j-1]); }
        if ( (m + n) % 2 == 1 ) { return maxLeft; }

        int minRight = 0;
        if (i == m) { minRight = nums2[j]; }
        else if (j == n) { minRight = nums1[i]; }
        else { minRight = Math.min(nums2[j], nums1[i]); }

        return (maxLeft + minRight) / 2.0;
    }
    }
    return 0.0;
}}
-2
对我来说，只需要几分钟写几行Python代码，就能通过LeetCode的检查，并且运行时间超过了62%的Python3在线提交。我的代码在这里：

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        n = len(nums1) + len(nums2)
        nums1.extend(nums2)  # merge two lists
        nums1.sort()  # sort it
        if n % 2 == 0:
            return (nums1[n//2-1] + nums1[n//2])/2 # return the median for even n
        else:
            return nums1[n//2] # return the median for odd n
1
哦，现在我知道我错了。我的解决方案的时间复杂度是O(n log(n))，但问题要求一个O(log (n))的解决方案。 - jliu1999
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接