力扣-4-寻找两个正序数组的中位数

中位数的定义是什么？有序数列中位置中间的数字
如果中间位置有两个返回则他们的平均值，所以这里的返回值是个double
要求时间复杂度为log(m+n)，也就是说只对两个数组做一次遍历，可以使用额外的空间，但是不能做额外的扫描
我想到了快速插入排序

扫描两个数组并做快速插入排序，但是其实我并不需要保存结果，我只需要保存我想要的数就行
原理是快排每一次划分得到的基准的索引在后面的排序过程中是不变的

注意到这里给出的两个数组都是正序的，那得用上

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {

	double res;

	int m = nums1.size(), n = nums2.size();
	int count = (m + n) / 2;
	int i = 0, j = 0;
	while (count) {
		if (i < m && j < n) {
			if (nums1[i] > nums2[j]) j++;
			else i++;
		}
		// 考虑一个数组遍历完了，另一个数组很长的情况
		else if (i < m) {
			i++;
		}
		else j++;
		count--;
	}

	cout << i << j << endl;


	// 算出我想要得到的数字的索引
	if ((m + n) & 1) {
		// 长度为奇数，中位数只有1个
		if (i < m && j < n) res = max(nums1[i], nums2[j]);
		else if (i < m) res = nums1[i];
		else res = nums2[j];
	}
	else {
		// 长度为偶数，中位数两个
		if (i < m && j < n) {
			// 当前两个指向中较大的那个，加上它的下一个
		}
		else if (i < m) res = (nums1[i]+nums1[i+1])/2;
		else res = (nums2[j]+nums2[j+1])/2;
	}
	return res;
}

不行，感觉思路乱了，代码也很不好看

原文地址：http://www.cnblogs.com/yaocy/p/16832432.html