402v

最近在刷leetcode，对自己的算法思路做个简单的记录，希望最后回顾起来自己是有提高的。

通篇算法都是用Ruby语言实现，文内不再赘述。Markdown没有支持数学格式，所以时间复杂度的记法比较粗糙，见谅。

这一系列的文章可以在这里找到。

本期题目:

here 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)).

题目难度: Hard

找两个有序数组的中位数，要求算法的时间复杂度是O(log(m+n)).

#多些时间可以少些Code 看到有序数组就很开心了，算法要求时间复杂度是O(log(m+n))，也就是说最多将两个数组都遍历一次就要找到中值。

第一次思考思路就是将两个有序数组做merge：

假设两个数组都是从小到大有序排列（这样假设是合理的。因为既然是有序数组这件事情很好判断：选取第一个和最后一个元素比较即知道大小顺序，如果两个数组顺序相反则其中一个采用倒序索引即可。）

从前到后分别索引两个数组，用两个标记nums1_i、nums2_i记录当前的索引位置；
比较当前索引元素值的大小，将小的元素添加到新数组中；
记录新数组长度，当长度等于(m+n)/2时，当前值记为中值。

边界条件：

数组为空（单个数组为空或者都为空）；
m+n为奇数，中值为第 (m+n)/2 个元素；
m+n为偶数，中值为第（m+n）/2-1 和（m+n）/2 个元素的中值（除以2）

#还是要Code

# @param {Integer[]} nums1
# @param {Integer[]} nums2
# @return {Float}
def find_median_sorted_arrays(nums1, nums2)

	# 边界判断
	if nums1.length == 0 then
		if nums2.length == 0 then
			# 两个数组都为空
			return 0.0
		else
			# 只有nums1为空
			return find_median_array(nums2)
		end
	end
	
	if nums2.length == 0 then
		# 只有nums2为空
		return find_median_array(nums1)
	end

	nums1_i = 0
	nums2_i = 0
		
	res_nums = []
	
	while res_nums.length < (nums1.length + nums2.length)/2+1 && nums1_i < nums1.length && nums2_i < nums2.length do
		if nums1[nums1_i] < nums2[nums2_i] then
			res_nums << nums1[nums1_i]
			nums1_i += 1
		elsif
			res_nums << nums2[nums2_i]
			nums2_i += 1
		end
	end
	
	while res_nums.length < (nums1.length + nums2.length)/2+1 && nums1_i < nums1.length do
		res_nums << nums1[nums1_i]
		nums1_i += 1
	end
	
	while res_nums.length < (nums1.length + nums2.length)/2+1 && nums2_i < nums2.length do
		res_nums << nums2[nums2_i]
		nums2_i += 1
	end
	
#	puts("result:#{res_nums}")
	ret = 0.0
	if (nums1.length+nums2.length)%2 == 0 then
		ret = (res_nums[-2] + res_nums[-1])/2.0
	elsif
		ret = res_nums[-1]/1.0
	end
	
	ret
end

def find_median_array(nums)
	if nums.length == 0 then
		0.0
	elsif nums.length == 1 then
		nums[0]/1.0
	else
		ret = 0.0
		if nums.length%2 == 0 then
			ret = (nums[nums.length/2 - 1] + nums[nums.length/2])/2.0
		else
			ret = nums[nums.length/2]/1.0
		end
		return ret
	end
end

看到题目难度是hard就难住了，考虑了很多排序算法，还把堆排、快排都复习了一遍，后来怎么想都没思路所以就直接按照自己最初的想法Coding，没想到居然过了。。。还是不能想太多啊。。

LeetCode实战 - Median of Two Sorted Array

评论 · 0