划水 leetcode：4

前言

第三篇算法总结，总结 leetcode 第 3 题。

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

You may assume nums1 and nums2 cannot be both empty.

审题&思路

给定两个排好序的数组，各自的大小为 m、n，找到这两个排序后的数组的中位数，并且时间复杂度必须小于 O(log (m+n))。

直观思路

本题需要满足两个要求：

• 将两个数组排序，求排序后数组的中位数。
• 时间复杂度必须小于 O(log (m+n))。

所以，我第一直觉选用二叉树排序进行数组排序，然后求出排序后的数组的中位数。

解题

本题难易：难。

排序二叉树

struct TreeNode
{
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
   void insertTreeNode(TreeNode *&p, int val) {
		// cout << "Insert:" << val << endl;
		if (p == NULL) {
			p = new TreeNode(val);
		} 
		else if (val <= p->val) {			
			insertTreeNode(p->left, val);
		}
		else {
			insertTreeNode(p->right, val);
			return;
		}
	}

	void traverseTree(TreeNode *t) {
		if (t != NULL)
		{
			traverseTree(t->left);
			// cout << t->val << " ";
			traverseTree(t->right);
		}
	}

	void sortArray(TreeNode *t, std::vector<int> &v) {
		if (t != NULL)
		{
			sortArray(t->left, v);
			v.push_back(t->val);
			sortArray(t->right, v);
		}
	}

    
    double medianOfSortedArray(vector<int>& nums) {
    	double resault = 0.0;

    	if (nums.size() % 2 == 1)
    	{
    		
    		int index = (nums.size() + 1) / 2 - 1;
    		resault = (double)nums.at(index);
    		// cout << "Odd Number:" << nums.at(index) << endl;
    	} else {
    		int i0 = nums.size() / 2 - 1;
    		int i1 = nums.size() / 2;

    		double sum = (double)nums.at(i0) + (double)nums.at(i1);
    		// cout << "sum: " << sum << endl;
    		resault = (double)(sum) / 2.0;

    		// cout << "Even Number: 1/2*(" << nums.at(i0) << "+" << nums.at(i1) << ") = " << resault << endl;
    	}

    	return resault;
    }

    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    	double resault = 0.0;
		std::vector<int> unsortVector;
	    unsortVector.insert(unsortVector.end(), nums1.begin(), nums1.end());
	    unsortVector.insert(unsortVector.end(), nums2.begin(), nums2.end());
	    TreeNode *t = NULL;
	    for (std::vector<int>::iterator i = unsortVector.begin(); i < unsortVector.end(); ++i)
	    {
	    	insertTreeNode(t, *i);
	    }
	    std::vector<int> sortedArray;

	    sortArray(t, sortedArray);
	    // cout << "====== Finish Sort ======" << endl;
	    // for (std::vector<int>::iterator i = sortedArray.begin(); i != sortedArray.end(); ++i)
	    // {
	    // 	cout << *i << " ";
	    // }

	    resault = medianOfSortedArray(sortedArray);
    	return resault;
    }

};

二叉查找树（英语：Binary Search Tree），也称为二叉搜索树、有序二叉树（ordered binary tree）或排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：

• 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
• 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
• 任意节点的左、右子树也分别为二叉查找树；
• 没有键值相等的节点。

中序遍历二叉查找树可得到一个关键字的有序序列，一个无序序列可以通过构造一棵二叉查找树变成一个有序序列，构造树的过程即为对无序序列进行查找的过程。每次插入的新的结点都是二叉查找树上新的叶子结点，在进行插入操作时，不必移动其它结点，只需改动某个结点的指针，由空变为非空即可。搜索、插入、删除的复杂度等于树高，期望 O(log n)，最坏 O(n) （数列有序，树退化成线性表）。

其中，除了中序遍历(In-Order Traversal)，还有前序遍历前序遍历(Pre-Order Traversal)和后序遍历(Post-Order Traversal)，这三种遍历都属于深度优先搜索(Depth-First-Search，DFS)。

根据二叉查找树的时间复杂度，中位数排序数组的二叉树排序的时间复杂度应该为 O(log(m+n))，满足了题目的最低要求。但是，虽然上述算法通过了，其算法的性能只打败了 5% 的算法，所以，继续研习 Solution 中的算法解。

Recursive Approach

官方给的解更倾向于数学分析，推理过程如下。

假设集合 A={}