查詢兩個(gè)數(shù)組的中位數(shù)

Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:

nums1 = [1, 3]

nums2 = [2]

The median is 2.0

Example 2:

nums1 = [1, 2]

nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

思路

給定nums1給nums2，則中位數(shù)的位置一定能確定，len(nums1) + len(nums2) / 2的取整值，記為median_idx

需要區(qū)分是len(nums1) + len(nums2)是奇數(shù)還是偶數(shù)

兩個(gè)指針，只需要從nums1和nums2頭部開始往后移動(dòng)，將兩者中較小值放入新的數(shù)組

當(dāng)新的數(shù)組的長度達(dá)到了median_idx，即可求中位數(shù)

過程中需要注意兩個(gè)數(shù)組長度不等的情況，防止下標(biāo)越界

代碼

class Solution(object):

def findMedianSortedArrays(self, nums1, nums2):

"""

:type nums1: List[int]

:type nums2: List[int]

:rtype: float

"""

median_idx = int((len(nums1) + len(nums2)) / 2)

index1, index2 = 0, len(nums1)

combine_list = nums1 + nums2

new_list = []

i = 0

while i <= median_idx:

if index1 < len(nums1) and index2 - len(nums1) < len(nums2):

new_list.append(min(combine_list[index1], combine_list[index2]))

if combine_list[index1] < combine_list[index2]:

index1 += 1

else:

index2 += 1

elif index1 >= len(nums1):

# nums1 is out of range, append nums2

new_list.append(combine_list[index2])

index2 += 1

elif index2 >= len(nums2):

# nums2 is out of range, append nums1

new_list.append(combine_list[index1])

index1 += 1

i += 1

if (len(nums1) + len(nums2)) % 2 == 0:

median = float(new_list[median_idx] + new_list[median_idx - 1]) / 2

else:

median = new_list[median_idx]

return median

本題以及其它leetcode題目代碼github地址: github地址

總結(jié)

以上是生活随笔為你收集整理的java 两个等长数组的中位数_查询两个数组的中位数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。