绵阳市淘金网络科技有限公司
首页 | 联系方式 | 加入收藏 | 设为首页 | 手机站

产品目录

联系方式

联系人:业务部
电话: 00143- 858031
邮箱:service@zmkuykj.com

当前位置:首页 >> 产品展示 >> 默认分类 >> 正文

「每日一道算法题」Median of Two Sorted Arrays

详细信息:

Algorithm

OJ address

Leetcode website : 4. Median of Two Sorted Arrays

Description

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

You may assume nums1 and nums2 cannot be both empty.

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

Solution in C

第一种解法:

#include <stdio.h>
int a[5000];
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
 int index1 = 0;
 int index2 = 0;
 int index3 = 0;
 while(index1<nums1Size && index2<nums2Size) {
 if (nums1[index1]<nums2[index2]) {
 a[index3++] = nums1[index1++];
 }
 else {
 a[index3++] = nums2[index2++];
 }
 }
 while (index1<nums1Size) {
 a[index3++] = nums1[index1++];
 }
 while (index2<nums2Size) {
 a[index3++] = nums2[index2++];
 }
 if ((index3 % 2) != 0) {
 return a[(index3-1)/2];
 }
 else {
 return (a[index3/2]+a[index3/2-1])/2.0;
 } 
}
int main(int argc, char const *argv[])
{
 int c[2] = {1,3};
 int b[2] = {2};
 double dd = findMedianSortedArrays(c,2,b,1);
 printf("dd:%g\n", dd);
 return 0;
}

第二种解法:

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
 int index1, index2, index3, index5, index6, res, resA, resB;
 index1 = index2 = index3 = index5 = index6 = res = resA = resB = 0;
 int length = nums1Size + nums2Size;
 if (length%2!=0) {
 index5 = (length-1)/2;
 index6 = 0;
 }
 else {
 index5 = res = length/2;
 index6 = length/2-1;
 }
 for (int i=0;i<length;++i) {
 if (index1<nums1Size && index2<nums2Size) {
 if (nums1[index1] < nums2[index2]) res = nums1[index1++];
 else res = nums2[index2++];
 }
 else if (index1<nums1Size) res = nums1[index1++];
 else res = nums2[index2++];
 if (i == index5) resA = res;
 if (i == index6) resB = res;
 }
 return (length%2!=0) ? resA : ((resA + resB)/2.0);
}

Solution in Python

class Solution(object):
 def findMedianSortedArrays(self, nums1, nums2):
 i = 0
 j = 0
 length = len(nums1)+len(nums2)
 if length%2!=0:
 res = (length-1)/2
 respre = 0
 else:
 res = length/2
 respre = length/2-1
 for x in range(length):
 if i < len(nums1) and j < len(nums2):
 if nums1[i] < nums2[j]:
 dd = nums1[i]
 i = i+1
 else:
 dd = nums2[j]
 j = j+1
 elif i < len(nums1):
 dd = nums1[i]
 i = i+1
 elif j < len(nums2):
 dd = nums2[j]
 j = j+1
 if x == res:
 resA = dd
 break
 if x == respre:
 resB = dd
 if length%2!=0: 
 return resA 
 else: 
 return (resA + resB)/2.0
 
if __name__ == '__main__':
 a = Solution()
 d1 = [1,2]
 d2 = [3]
 c = a.findMedianSortedArrays(d1,d2)
 print c

My Idea

题目含义是,给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 。请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n)) 。

关于复杂度的理解就是,不要用排序去做,一次遍历解决这道题目,其实不用一遍遍历也可以解决这个题目,我写了两个解法:

  1. 第一种解法就是全部遍历,在遍历的时候比较两个数组每各元素的大小,将最小的元素存到新的数组中,然后遍历结束,在新的数组中找到中位数即可。算法的时间复杂度是O(m+n)
  2. 显然第一种解法是全部遍历,但是还有更好的方法,就是不用开数组,仅仅比较给到的两个数组,由于给到的数组长度是题目给你的,那中位数的位置也是固定的了,其实就是比较两个数组,一直比较到中位数的那个位置,然后保存中位数,直接返回结果就可以了。中位数的位置就是两个数组中间的位置。所以时间复杂度是O((m+n)/2),比第一种方法快一倍。而且不用开数组保存,大大的节约了空间复杂度。只要开变量保存结果就可以了。