Daily-Interview-Question
Daily-Interview-Question copied to clipboard
Published
20 hours ago •
Advanced-Frontend
Advanced-Frontend
第 93 题：给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log(m+n))。
示例 1：
nums1 = [1, 3]
nums2 = [2]
中位数是 2.0
示例 2：
nums1 = [1, 2]
nums2 = [3, 4]
中位数是(2 + 3) / 2 = 2.5
想到一个 O(n) 的解法，类似归并排序，抛砖引玉
const findMedianSortedArrays = function(
nums1: number[],
nums2: number[]
) {
const lenN1 = nums1.length;
const lenN2 = nums2.length;
const median = Math.ceil((lenN1 + lenN2 + 1) / 2);
const isOddLen = (lenN1 + lenN2) % 2 === 0;
const result = new Array<number>(median);
let i = 0; // pointer for nums1
let j = 0; // pointer for nums2
for (let k = 0; k < median; k++) {
if (i < lenN1 && j < lenN2) {
// tslint:disable-next-line:prefer-conditional-expression
if (nums1[i] < nums2[j]) {
result[i + j] = nums1[i++];
} else {
result[i + j] = nums2[j++];
}
} else if (i < lenN1) {
result[i + j] = nums1[i++];
} else if (j < lenN2) {
result[i + j] = nums2[j++];
}
}
if (isOddLen) {
return (result[median - 1] + result[median - 2]) / 2;
} else {
return result[median - 1];
}
};
加了注释，好理解一点，时间复杂度O(log(n+m))：
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number}
*/
var findMedianSortedArrays = function(nums1, nums2) {
let m = nums1.length
let n = nums2.length
let k1 = Math.floor((m + n + 1) / 2)
let k2 = Math.floor((m + n + 2) / 2)
return (findMedianSortedArraysCore(nums1, 0, nums2, 0, k1) + findMedianSortedArraysCore(nums1, 0, nums2, 0, k2)) / 2
};
/**
*
* @param {number[]} nums1
* @param {number[]} nums2
* @param {number} i
* @param {number} j
* @param {number} k
* @return {number}
*/
const findMedianSortedArraysCore = (nums1, i, nums2, j, k) => {
// 如果数组起始位置已经大于数组长度-1
// 说明已经是个空数组
// 直接从另外一个数组里取第k个数即可
if (i > nums1.length - 1) {
return nums2[j + k - 1]
}
if (j > nums2.length - 1) {
return nums1[i + k - 1]
}
// 如果k为1
// 就是取两个数组的起始值里的最小值
if (k === 1) {
return Math.min(nums1[i], nums2[j])
}
// 取k2为(k/2)或者数组1的长度或者数组2的长度的最小值
// 这一步可以避免k2大于某个数组的长度（长度为从起始坐标到结尾）
let k2 = Math.floor(k / 2)
let length1 = nums1.length - i
let length2 = nums2.length - j
k2 = Math.min(k2, length1, length2)
let value1 = nums1[i + k2 - 1]
let value2 = nums2[j + k2 - 1]
// 比较两个数组的起始坐标的值
// 如果value1小于value2
// 就舍弃nums1前i + k2部分
// 否则舍弃nums2前j + k2部分
if (value1 < value2) {
return findMedianSortedArraysCore(nums1, i + k2, nums2, j, k - k2)
} else {
return findMedianSortedArraysCore(nums1, i, nums2, j + k2, k - k2)
}
}
leetcode提交，算法耗时190ms
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number}
*/
var findMedianSortedArrays = function(nums1, nums2) {
let num = nums1.concat(nums2);
num = num.sort((a, b) => a - b);
let mid = Math.floor(num.length / 2);
if (num.length % 2 === 0) {
return (num[mid-1] + num[mid])/2
} else {
return num[mid]
}
};
function getMidPointNumber (arr1, arr2) {
const result = []
const len1 = arr1.length
const len2 = arr2.length
let i = 0
let j = 0
let count = 0
while (true) {
if (i == len1 && j == len2) {
break
}
if (i < len1 && j < len2 && arr1[i] <= arr2[j]) {
result.push(arr1[i])
i++
} else if (i < len1 && j < len2 && arr2[j] < arr1[i]) {
result.push(arr2[j])
j++
} else if (i === len1 && j < len2) {
while (j < len2) {
result.push(arr2[j])
j++
}
} else if (j === len2 && i < len1) {
while (i < len1) {
result.push(arr1[i])
i++
}
}
}
const mid = (len1 + len2) / 2
if ((len1 + len2) % 2 === 1 ) {
return result[mid]
} else {
return ((result[mid] + result[mid + 1]) / 2)
}
}
function mid(arr1, arr2) {
function findIndex(kArray) {
let value;
let tmp = 0;
let k = kArray[tmp];
let result = [];
function find(arr, i, j) {
if (i < j) {
let left = i;
let right = j;
let pivot = arr[left];
while (i < j) {
while (arr[j] < pivot && i < j) j--
// 交换位置
if (i < j) arr[i++] = arr[j];
while (arr[i] > pivot && i < j) i++;
if (i < j) arr[j--] = arr[i];
}
arr[i] = pivot;
if (i === k) {
value = arr[i];
}
if (i - 1 == left && i > k) {
value = arr[left];
}
if (i + 1 == right && i < k) {
value = arr[right];
}
// 找到第一位之后，再找下一位，只需要在当前位置之后查找，不用重新循环数组
// 因为我的入参是从小到大的
if (value) {
result.push(value);
value = undefined;
if (tmp == kArray.length - 1) return;
k = kArray[++tmp];
if (i == k) {
result.push(arr[i]);
return;
}
if (right == k) {
result.push(arr[right]);
return;
}
}
// 从左边找
if (i > k) find(arr, left, i - 1);
// 从右边找
if (i < k) find(arr, i + 1, right);
}
}
find(arr, 0, arr.length - 1);
return result;
}
var arr = arr1.concat(arr2);
var k = [];
if (arr.length % 2 == 0) k = [arr.length / 2 - 1, arr.length / 2];
else k = [Math.floor(arr.length / 2)];
var d = findIndex(k);
return d.length == 1 ? d[0] : (d[0] + d[1]) / 2;
}
思路是分治查找，利用类似TopK的思路，连续找两个指定的数，复杂度是O( log(m+n)) 首先concat数组，然后判断数组长度是奇数偶数 奇数直接找第n/2位 偶数找n/2-1,n/2位 除2
function findMiddleNumber (nums1, nums2) {
let length = nums1.length + nums2.length
let index_1 = 0
let index_2 = 0
let merge = []
while (length >= 0) {
if (index_1 >= nums1.length || index_2 >= nums2.length) {
break
}
if (nums1[index_1] < nums2[index_2]) {
merge.push(nums1[index_1])
index_1++
} else {
merge.push(nums2[index_2])
index_2++
}
length--
}
if (index_1 < nums1.length) {
merge = merge.concat(nums1.splice(index_1))
} else {
merge = merge.concat(nums2.splice(index_2))
}
let middleIndex = Math.floor(merge.length / 2)
if (merge.length % 2 === 0) {
return (merge[middleIndex] + merge[middleIndex - 1]) / 2
}
return merge[middleIndex]
}
| 提交结果 | 执行用时 |
|---|---|
| 通过 | 152 ms |
@xiongchenf 兄弟，你用了sort之后时间复杂度已经是O(nlog(n))了，不符合题目O(log(m+n))
大神是如何验证时间复杂度为 O(log(m+n)) ？？？
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number}
*/
var findMedianSortedArrays = function (nums1, nums2) {
var nums = []
while (nums1.length && nums2.length) {
if (nums1[0] < nums2[0]) {
nums.push(nums1.shift())
} else {
nums.push(nums2.shift())
}
}
nums = nums.concat(nums1, nums2)
var median
if (nums.length % 2) {
median = nums[Math.floor(nums.length / 2)]
} else {
var m = nums.length / 2
median = (nums[m - 1] + nums[m]) / 2
}
return median
}
Runtime: 108 ms
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number}
*/
var findMedianSortedArrays = function(nums1, nums2) {
let len1 = nums1.length;
let len2 = nums2.length;
let len = len1 + len2;
if(len === 0){
throw 'lalalal';
}
let lastNum = 0;
let targetLenIsOdd = isOdd(len);
let targetIndexEntry = targetLenIsOdd ? len / 2 | 0 : len / 2 - 1;
let result = [];
for(let i = 0,j = 0,s = 0; i < len1 || j < len2;){
if(i !== len1 && j !== len2){
if(nums1[i] < nums2[j]){
lastNum = nums1[i];
i++;
} else {
lastNum = nums2[j];
j++;
}
} else if(i !== len1){
lastNum = nums1[i];
i++;
} else {
lastNum = nums2[j];
j++;
}
if(targetIndexEntry <= s){
result.push(lastNum);
if(targetLenIsOdd){
result = result[0];
break;
} else {
if(targetIndexEntry + 1 === s){
result = (result[0] + result[1]) / 2;
break;
}
}
}
s ++;
}
return result;
};
function isOdd(num){
return num % 2 === 0 ? false : true;
}
//利用二分法，舍弃最小的一部分和舍弃最大的一部分，递归调用，完成输出。
// 时间复杂度 O(log2(m+n))
// js中Math.log默认是以自然数e为底数，并不是以2为底数，可能会造成误导
const num1=[1,2,5,8,9,10,11];
const num2=[3,4,9,12,19,30,31];
function findMedian(num1,num2) {
let center1Index = ~~(num1.length/2);
let center2Index = ~~(num2.length/2);
let center1=num1[center1Index];
let center2=num2[center2Index];
center1 = num1.length%2?center1:center1/2+(center1Index>0?num1[center1Index-1]:0)/2;
center2 = num2.length%2?center2:center2/2+(center2Index>0?num2[center2Index-1]:0)/2;
if(center1===center2){
return center1
}
if(num1.length===0){
return center2
}
if(num2.length===0){
return center1
}
if(num1.length===1&&num2.length===1){
return (center1+center2)/2
}else if(num1.length===1){
if(center1<num2[center2Index]){
num2.splice(center2Index-(center1>num2[center2Index-1]?2:1),0,center1)
}else {
num2.splice(center2Index+(center1>num2[center2Index+1]?1:0),0,center1)
}
return findMedian([],num2);
}else if(num2.length===1){
if(center2<num1[center1Index]){
num1.splice(center1Index-(center2>num1[center1Index-1]?2:1),0,center2)
}else {
num1.splice(center1Index+(center2>num1[center1Index+1]?1:0),0,center2)
}
return findMedian(num1,[]);
}
let rightIsMax = center2>center1;
let spliceNumber=Math.min(center1Index,center2Index,rightIsMax?-center2Index+num2.length-1:center2Index,rightIsMax?center1Index:-center1Index+num1.length-1)||1;
if(rightIsMax){
num2=num2.slice(0,-spliceNumber);
num1=num1.slice(spliceNumber);
}else {
num1=num1.slice(0,-spliceNumber);
num2=num2.slice(spliceNumber);
}
return findMedian(num1,num2);
}
findMedian(num1,num2);
力扣上一道题，不会做 https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/xun-zhao-liang-ge-you-xu-shu-zu-de-zhong-wei-shu-b/
var findMedianSortedArrays = function(nums1, nums2) {
return find2Middle(nums1, nums2)
}
var findMiddle = (arr) => {
let L = arr.length
if (L < 3) return sum(arr)/L
newArr = arr.slice(1, -1)
return findMiddle(newArr)
}
var sum = (arr) => arr.reduce((a, c) => a + c, 0)
var find2Middle = (M, N) => {
let LengthM = M.length, LengthN = N.length
if (LengthM === 0) return findMiddle(N)
if (LengthN === 0) return findMiddle(M)
if (LengthM + LengthN === 2) return (M[0]+N[0])/2
let newM = M, newN = N;
let ML = M[0], MH = M[LengthM - 1];
let NL = N[0], NH = N[LengthN - 1];
if (ML <= NL) newM = M.slice(1);
if (ML > NL) newN = N.slice(1);
if (MH <= NH) newN = newN.slice(0, -1);
if (MH > NH) newM = newM.slice(0, -1);
return find2Middle(newM, newN);
}
随便写的, 求大神指点
| 2084 / 2084 test cases passed. | Status: Accepted |
|---|---|
| Runtime: 120 msMemory Usage: 69.6 MB | Submitted: 12 minutes ago |
这是一个leetcode原题， 题目链接：https://leetcode.com/problems/median-of-two-sorted-arrays .
官方中文版链接： https://leetcode-cn.com/problems/median-of-two-sorted-arrays/
以下我的答案：
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number}
*/
function findKth(nums1, nums2, k) {
if (nums1.length === 0) return nums2[k - 1];
if (nums2.length === 0) return nums1[k - 1];
if (k == 1) return Math.min(nums1[0], nums2[0]);
let i = Math.min(k >> 1, nums1.length);
let j = Math.min(k >> 1, nums2.length);
if (nums1[i - 1] > nums2[j - 1]) {
return findKth(nums1, nums2.slice(j), k - j);
}
return findKth(nums1.slice(i), nums2, k - i);
}
var findMedianSortedArrays = function(nums1, nums2) {
// 1
// 2 3 4 5
const m = nums1.length,
n = nums2.length;
return (
(findKth(nums1, nums2, (m + n + 1) >> 1) +
findKth(nums1, nums2, (m + n + 2) >> 1)) /
2.0
);
};
如果大家对算法有兴趣，可以关注下我的仓库《leetcode题解》
// 时间复杂度为O(M+N)的依次比较排序
function sortMN(arr1,arr2) {
let i=j=0;
const arr1length = arr1.length;
const arr2length = arr2.length;
let arr = [];
while(i< arr1length && j< arr2length) {
if (arr1[i] < arr2[j]){
arr.push(arr1[i])
i++
} else {
arr.push(arr2[j])
j++
}
}
if(i === arr1length){
arr.concat(arr2.slice(j));
} else {
arr.concat(arr1.slice(i))
}
return arr
}
function middleNumber(arr1,arr2) {
let arr = sortMN(arr1,arr2);
let arrLength = arr.length;
if (arrLength % 2 === 0) {
return (arr[arrLength/2] + arr[arrLength/2-1]) / 2.00
} else {
eturn arr[arrLength/2]
}
}
题目已经说明了是两个有序数组，那可以按照归并排序的方法进行数组合并
function findMiddle(arr1,arr2){
var result = [];
while(arr1.length && arr2.length){
if(arr1[0]<arr2[0]){
result.push(arr1[0]);
arr1.shift();
}else{
result.push(arr2[0]);
arr2.shift();
}
}
if(arr1.length){
result = result.concat(arr1);
}
if(arr2.length){
result = result.concat(arr2);
}
return result.length%2===0
? (result[Math.floor(result.length/2)-1] + result[Math.floor(result.length/2)])/2
: result[Math.floor(result.length/2)];
}
对于一个有序数组来说，
如果数据的个数是奇数，则中间那个数据就是这群数据的中位数； 如果数据的个数是偶数，则中间那2个数据的算术平均值就是这群数据的中位数 所以我们首先要将两个有序数组进行合并，再进行中位数计算
function sort(arr1, arr2) {
let index1 = 0 // 数组1下标
let index2 = 0 // 数组2下标
let arr = [] // 合并后的数组
// 只要有一个有序数组的下标和该数组长度相等，就停止循环♻️
while(index1 < arr1.length && index2 < arr2.length) {
if(arr1[index1] < arr2[index2]) {
arr.push(arr1[index1])
index1++
} else {
arr.push(arr2[index2])
index2++
}
}
// 判断是哪个数组的下标和长度相等，再将另一个数组进行合并
if(index1 === arr1.length) {
// concat不会改变现有的数组，而仅仅会返回被连接数组的一个副本，所以需要重新赋值给arr
arr = arr.concat(arr2.slice(index2, arr2.length))
}
if(index2 === arr2.length) {
arr = arr.concat(arr1.slice(index1, arr1.length))
}
if(arr.length % 2 === 0) {
return (arr[arr.length / 2] + arr[arr.length / 2 - 1]) / 2
}else {
return arr[Math.floor(arr.length / 2)]
}
}
function mid (arr1, arr2) { const len1 = arr1.length; const len2 = arr2.length;
const len = len1 + len2;
let arr = [];
let i = 0, j = 0, k = 0;
while(i < len1 && j < len2 && k < len) {
if (arr1[i] < arr2[j]) {
arr[k++] = arr1[i++];
} else {
arr[k++] = arr2[j++];
}
}
if (i < len1) {
arr = [...arr, ...arr1.slice(i)];
}
if (j < len2) {
arr = [...arr, ...arr2.slice(j)];
}
if (len % 2 == 0) {
return (arr[Number.parseInt(len / 2) - 1] + arr[Number.parseInt(len / 2) + 1]) / 2;
} else {
return arr[Number.parseInt(len / 2)];
}
}
大佬们 我这个能否达标？
leetcode上 144ms-208ms 之间 符合O(log(m+n))这个复杂度吗？ 我的思路： 两个数组依次比较同时用n1、n2记住位置 当比较次数达到两个数组总长度一半时返回结果
var findMedianSortedArrays = function (nums1, nums2) {
let sum = nums1.length + nums2.length,
count = 0,
n1 = 0,
n2 = 0,
half = Math.floor(sum / 2 + 1),
res = [];
while (count < half) {
if (nums1[n1] <= nums2[n2] || nums2[n2] === undefined) {
res.push(nums1[n1])
n1++;
} else {
res.push(nums2[n2])
n2++;
}
count++;
}
if (sum % 2 == 0) {
return (res[res.length - 1] + res[res.length - 2]) / 2;
} else {
return res[res.length - 1];
}
};
function midNum(nums1, nums2){
let nums = [...nums1, ...nums2];
nums.sort((a, b) => a-b)
let length = nums.length;
if(length % 2 == 1){
return nums[(length-1)/2]
}
return (nums[length/2]+nums[length/2-1])/2;
}
function middle(arr1, arr2) {
let o = arr1.concat(arr2).sort(function (a,b) {
return a - b
});
let middleNum;
if (o.length % 2 === 0) { // 偶数
middleNum = (o[o.length / 2] + o[o.length / 2 - 1]) / 2
} else { // 奇数
middleNum = o[parseInt(o.length / 2)]
}
console.log(`中位数为 ${middleNum}`);
}
先合并两个有序数组
var mergetTwoArrays = (nums1, nums2) =>{
var i = 0
var m = 0, lenM = nums1.length
var n = 0, lenN = nums2.length
var arr = []
while(m < lenM && n < lenN) {
if (nums1[m] <= nums2[n]) {
arr[i++] = nums1[m++]
} else {
arr[i++] = nums2[n++]
}
}
while(n < lenN) {
arr[i++] = nums2[n++]
}
while(m < lenM) {
arr[i++] = nums1[m++]
}
return arr
}
然后求中位数，但是时间复杂度为O(m + n)
类似归并排序最后一大步的思路，不排序直接找中位数 逐步去除最大最小数，逼近中位数
const quickMid = (nums1, nums2) => {
let n = Math.ceil((nums2.length + nums1.length) / 2)
let i1Start = i2Start = 0
let i1End = nums1.length -1, i2End = nums2.length - 1
let newNum
for (let i = 0; i < n - 1; i++) { // n-1 最后一组不比较
let min1 = nums1[i1Start]
let min2 = nums2[i2Start]
min1 === undefined || min1 > min2 ? i2Start++ : i1Start++
let max1 = nums1[i1End]
let max2 = nums2[i2End]
max1 === undefined || max2 > max1 ? i2End-- : i1End--
// 一组先结束取另一组剩余值
if (i1Start > i1End) {
newNum = nums2.slice(i2Start, i2End + 1)
break
} else if (i2Start > i2End) {
newNum = nums1.slice(i1Start, i1End + 1)
break
}
}
if (newNum) {
let l = newNum.length
let mid = Math.ceil(l / 2)
if (l % 2 === 0) {
return (newNum[mid] + newNum[mid - 1]) / 2
} else {
return newNum[mid - 1]
}
} else {
num1 = i1Start === i1End ? nums1[i1End] : nums1[i1Start + 1]
num2 = i2Start === i2End ? nums2[i2End] : nums2[i2Start + 1]
return (num1 + num2) / 2
}
}
思路：只要找到这两个有序数组的中位数，那么我们可以首先算出两个数组的长度和，然后推算出中位数所在的索引，如果长度为奇数，那么就是n/2,如果是偶数，那么是n/2 和n/2-1，我们对两个数组进行排序时（因为已经是有序数组，所以可以采用类似归并的算法，整合两个数组，循环结束条件即为数组长度=中位数的索引+1），然后最后得到中位数， 这样可以吗？ const nums1 = [1, 5, 5.5, 7, 8, 9] const nums2 = [2, 3, 5, 6, 8.5, 10]
const len = Math.round((nums1.length + nums2.length) / 2) const res = [] let i = 0, j = 0 while (res.length <= len + 1) { // 合并两个有序数组 if (nums1[i] < nums2[j]) { res.push(nums1[i]) i++ } else { res.push(nums2[j]) j++ } } console.log(res) if ((nums1.length + nums2.length) % 2) { //奇数位 console.log(res[len - 1]) } else { //偶数位 console.log((res[len] + res[len - 1]) / 2) }
let list1 = [1, 3, 5]
let list2 = [2]
let allLeng = list2.length + list1.length
// 循环最大次数
let maxCount = (allLeng / 2) | 0
let count = 0
let prev = null
let current = null
let result = null
while (count <= maxCount) {
count++
prev = current
if (list1.length === 0) {
current = list2.shift()
} else if (list2.length === 0) {
current = list1.shift()
} else if (list1[0] < list2[0]) {
current = list1.shift()
} else {
current = list2.shift()
}
}
if (allLeng % 2 === 0) { // 偶数个
result = (prev + current) / 2
} else { // 奇数个
result = current
}
console.log(result)
function findMedianSortedArrays(nums1, nums2) {
let [{ length: m }, { length: n }] = [nums1, nums2];
if (m > n) {
[m, n] = [n, m];
[nums1, nums2] = [nums2, nums1];
}
let [imin, imax] = [0, m];
const halfLen = (m + n + 1) / 2;
while (imin <= imax) {
let i = ~~((imin + imax) / 2);
let j = ~~(halfLen - i);
if (i < imax && nums2[j - 1] > nums1[i]) {
imin = i + 1;
} else if (i > imin && nums1[i - 1] > nums2[j]) {
imax = i - 1;
} else {
let maxLeft;
if (!i) {
maxLeft = nums2[j - 1];
} else if (!j) {
maxLeft = nums1[i - 1];
} else {
maxLeft = Math.max(nums1[i - 1], nums2[j - 1]);
}
if ((m + n) % 2) {
return maxLeft;
}
let minRight;
if (i === m) {
minRight = nums2[j];
} else if (j === n) {
minRight = nums1[i];
} else {
minRight = Math.min(nums2[j], nums1[i]);
}
return (maxLeft + minRight) / 2;
}
}
}
// 一个O(n) 的解法，在排序的基础上做二路归并。
var num1 = [1, 2, 5, 7, 10];
var num2 = [3, 4, 5, 6, 8, 9];
console.log(findMedian(num1, num2));
function findMedian(arr1, arr2) {
var arr = [];
if (arr1[0] >= arr2[arr2.length - 1]) {
arr = [...arr2, ...arr1];
} else if (arr1[arr1.length - 1] <= arr2[0]) {
arr = [...arr1, ...arr2];
} else {
var arr_i = 0;
var arr1_i = 0;
for (var arr2_i = 0; arr2_i < arr2.length; arr2_i ++) {
if (arr1[arr1_i] < arr2[arr2_i]) {
arr[arr_i] = arr1[arr1_i];
arr_i ++;
arr1_i ++;
arr2_i --;
} else {
arr[arr_i] = arr2[arr2_i];
arr_i ++;
}
}
if (arr2_i == arr2.length) {
for (var i = arr1_i; i < arr1.length; i ++) {
arr[arr_i] = arr1[i];
arr_i ++;
}
} else {
for (var i = arr2_i; i < arr2.length; i ++) {
arr[arr_i] = arr2[i];
arr_i ++;
}
}
}
if (arr.length % 2 == 0) {
return (arr[Math.floor((arr.length - 1) / 2)] + arr[Math.floor(arr.length / 2)]) / 2;
} else {
return arr[Math.floor(arr.length / 2)];
}
}
代码不复杂，就是原本想能一行写完写成了这样，有点难读
const findMedianSortedArrays = (nums1, nums2) => {
let len = nums1.length + nums2.length
if (len <= 2) return ((nums1.length === 0 ? 0 : nums1.reduce((x, val) => x + val)) + (nums2.length === 0 ? 0 : nums2.reduce((x, val) => x + val))) / len;
((nums1.lenght !== 0 && (nums2.length ===0 || (nums1[nums1.length - 1] > nums2[nums2.length - 1]))) ?nums1 : nums2).pop();
(nums1.length !== 0 && (nums2.length === 0 || (nums1[0] < nums2[0])) ? nums1 : nums2).shift()
return findMedianSortedArrays(nums1, nums2)
}
- 执行用时 :132 ms, 在所有 JavaScript 提交中击败了75.54%的用户
- 内存消耗 :39.4 MB, 在所有 JavaScript 提交中击败了93.75%的用户
或者不用递归
const findMedianSortedArrays = (nums1, nums2) => {
while (nums1.length + nums2.length > 2) {
((nums1.lenght !== 0 && (nums2.length === 0 || (nums1[nums1.length - 1] > nums2[nums2.length - 1]))) ? nums1 : nums2).pop();
(nums1.length !== 0 && (nums2.length === 0 || (nums1[0] < nums2[0])) ? nums1 : nums2).shift()
}
return ((nums1.length === 0 ? 0 : nums1.reduce((x, val) => x + val)) + (nums2.length === 0 ? 0 : nums2.reduce((x, val) => x + val))) / (nums1.length + nums2.length);
}
- 执行用时 :136 ms, 在所有 JavaScript 提交中击败了67.91%的用户
- 内存消耗 :39.3 MB, 在所有 JavaScript 提交中击败了93.75%的用户
/**
* 因为已经是有序数组，所以不需要递归调用来排序，只需要借鉴归并排序中两个有序数组合并的算法就可以
* @param {*} nums1
* @param {*} nums2
*/
function findMidValue(nums1, nums2) {
let nums = [];
//合并两个有序数组
while (nums1.length && nums2.length) {
if (nums1[0] < nums2[0]) {
nums.push(nums1.shift())
} else {
nums.push(nums2.shift());
}
}
if (nums1.length) {
nums.push(...nums1);
}
if (nums2.length) {
nums.push(...nums2);
}
let len = nums.length;
let midValue = 0;
console.log('nums:', nums);
if (len % 2 === 0) {
midValue = (nums[len / 2] + nums[len / 2 - 1]) / 2;
} else {
midValue = nums[Math.floor(len / 2)];
}
return midValue;
}
var nums1 = [1, 2]
var nums2 = [3, 4, 6, 8]
console.log(findMidValue(nums1, nums2));
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number}
*/
var findMedianSortedArrays = function(nums1, nums2) {
let index = 0;
let len = nums1.length + nums2.length;
let val0;
let val1;
let i = 0;
let j = 0;
let mid = ~~((len + 2) / 2);
while(index < mid){
val0 = val1;
if(i >= nums1.length){
val1 = nums2[j];
j ++;
}else if(j >= nums2.length){
val1 = nums1[i];
i ++;
}else if(nums1[i] >= nums2[j]){
val1 = nums2[j];
j ++;
}else{
val1 = nums1[i];
i ++;
}
index ++;
}
return len % 2 === 1 ? val1 : (val1 + val0)/2
};
120 ms
/** * @param {number[]} nums1 * @param {number[]} nums2 * @return {number} */ var findMedianSortedArrays = function (nums1, nums2) { var nums = [] while (nums1.length && nums2.length) { if (nums1[0] < nums2[0]) { nums.push(nums1.shift()) } else { nums.push(nums2.shift()) } } nums = nums.concat(nums1, nums2) var median if (nums.length % 2) { median = nums[Math.floor(nums.length / 2)] } else { var m = nums.length / 2 median = (nums[m - 1] + nums[m]) / 2 } return median }Runtime: 108 ms
请教一下，这个的复杂度不是O(log(m+n))吧，应该是O(m+n)
var findMedianSortedArrays = function(nums1, nums2) {
//先归并 归并结束求中位数
var arr = [];
while(nums1.length|| nums2.length){
if(nums1.length==0&&nums2.length){
arr = [...arr,...nums2];
break;
}
if(nums2.length==0&&nums1.length){
arr = [...arr,...nums1];
break;
}
if(nums1[0]<=nums2[0]){
arr.push(nums1.shift());
}else{
arr.push(nums2.shift());
}
}
var half = Math.ceil(arr.length/2);
if(arr.length%2==0){
return (arr[half] + arr[half-1])/2;
}else{
return arr[half-1];
}
};
/**
* 使用归并思想,时间复杂度O(log(m+n))
* @param {*} arr1
* @param {*} arr2
*/
const getMidPointNumber = (arr1, arr2) => {
let arr = []
let len = arr1.length + arr2.length
let index = 0
let mid = Math.floor(len / 2)
while (arr1.length > 0 || arr2.length > 0) {
if (index > mid) {
if (len % 2 !== 0) {
return arr[index - 1]
} else {
return (arr[index - 2] + arr[index - 1]) / 2
}
}
if (arr1.length > 0 && arr2.length > 0) {
arr.push(arr1[0] > arr2[0] ? arr2.shift() : arr1.shift())
} else if (arr1.length > 0) {
arr.push(arr1.shift())
} else {
arr.push(arr2.shift())
}
index++
}
if (arr.length === 1) return arr[0]
return (arr[0] + arr[1]) / 2
}
var findMedianSortedArrays = function (nums1, nums2) {
if (nums1.length > nums2.length) {
return findMedianSortedArrays(nums2, nums1);
}
var len1 = nums1.length;
var len2 = nums2.length;
var low = 0;
var high = len1;
while (low <= high) {
var p1 = Math.floor((low + high) / 2);
var p2 = Math.ceil((len1 + len2) / 2) - p1;
var maxLeft1 = p1 === 0 ? -Infinity : nums1[p1 - 1];
var minRight1 = p1 === len1 ? Infinity : nums1[p1];
var maxLeft2 = p2 === 0 ? -Infinity : nums2[p2 - 1];
var minRight2 = p2 === len2 ? Infinity : nums2[p2];
if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
if ((len1 + len2) % 2 === 0) {
return (
(Math.max(maxLeft1, maxLeft2) + Math.min(minRight1, minRight2)) / 2
);
} else {
return Math.max(maxLeft1, maxLeft2);
}
} else if (maxLeft1 > minRight2) {
high -= 1;
} else {
low += 1;
}
}
};
https://www.youtube.com/watch?v=LPFhl65R7ww 推荐这个视频，图文并茂，生动形象，容易理解，时间复杂度O(log min(m, n))
function findMiddle(arr1, arr2) {
let arr = [...arr1, ...arr2].sort((a,b)=> return a-b)
let num = arr.length%2
return num === 1 ? arr[Math.floor(len/2)] : (arr[arr.length/2]-1 + arr[arr.length/2])/2
}
arr = [1,2,3,4,5,6,7,8]
findMiddle(arr)
大顶堆+小顶堆
const defaultCmp = (x, y) => x > y; // 默认是大顶堆
const swap = (arr, i, j) => ([arr[i], arr[j]] = [arr[j], arr[i]]);
class Heap {
/**
* 默认是大顶堆
* @param {Function} cmp
*/
constructor(cmp = defaultCmp) {
this.container = [];
this.cmp = cmp;
}
insert(data) {
const { container, cmp } = this;
container.push(data);
let index = container.length - 1;
while (index) {
let parent = Math.floor((index - 1) / 2);
if (!cmp(container[index], container[parent])) {
return;
}
swap(container, index, parent);
index = parent;
}
}
extract() {
const { container, cmp } = this;
if (!container.length) {
return null;
}
swap(container, 0, container.length - 1);
const res = container.pop();
const length = container.length;
let index = 0,
exchange = index * 2 + 1;
while (exchange < length) {
// 以大顶堆的情况来说：如果有右节点，并且右节点的值大于左节点的值
let right = index * 2 + 2;
if (right < length && cmp(container[right], container[exchange])) {
exchange = right;
}
if (!cmp(container[exchange], container[index])) {
break;
}
swap(container, exchange, index);
index = exchange;
exchange = index * 2 + 1;
}
return res;
}
top() {
if (this.container.length) return this.container[0];
return null;
}
}
var MedianFinder = function () {
this.maxHeap = new Heap();
this.minHeap = new Heap((x, y) => x < y);
};
MedianFinder.prototype.addNum = function (num) {
this.maxHeap.insert(num);
this.minHeap.insert(this.maxHeap.top());
this.maxHeap.extract();
if (this.maxHeap.container.length < this.minHeap.container.length) {
this.maxHeap.insert(this.minHeap.top());
this.minHeap.extract();
}
};
MedianFinder.prototype.findMedian = function () {
return this.maxHeap.container.length > this.minHeap.container.length
? this.maxHeap.top()
: (this.maxHeap.top() + this.minHeap.top()) / 2;
};
// 使用
let finder = new MedianFinder()
let nums1 = [1, 2]
let nums2 = [3, 4]
for(let i of nums1){
finder.addNum(i)
}
for(let i of nums2){
finder.addNum(i)
}
console.log(finder.findMedian())
加了注释，好理解一点，时间复杂度O(log(n+m))：
/** * @param {number[]} nums1 * @param {number[]} nums2 * @return {number} */ var findMedianSortedArrays = function(nums1, nums2) { let m = nums1.length let n = nums2.length let k1 = Math.floor((m + n + 1) / 2) let k2 = Math.floor((m + n + 2) / 2) return (findMedianSortedArraysCore(nums1, 0, nums2, 0, k1) + findMedianSortedArraysCore(nums1, 0, nums2, 0, k2)) / 2 }; /** * * @param {number[]} nums1 * @param {number[]} nums2 * @param {number} i * @param {number} j * @param {number} k * @return {number} */ const findMedianSortedArraysCore = (nums1, i, nums2, j, k) => { // 如果数组起始位置已经大于数组长度-1 // 说明已经是个空数组 // 直接从另外一个数组里取第k个数即可 if (i > nums1.length - 1) { return nums2[j + k - 1] } if (j > nums2.length - 1) { return nums1[i + k - 1] } // 如果k为1 // 就是取两个数组的起始值里的最小值 if (k === 1) { return Math.min(nums1[i], nums2[j]) } // 取k2为(k/2)或者数组1的长度或者数组2的长度的最小值 // 这一步可以避免k2大于某个数组的长度（长度为从起始坐标到结尾） let k2 = Math.floor(k / 2) let length1 = nums1.length - i let length2 = nums2.length - j k2 = Math.min(k2, length1, length2) let value1 = nums1[i + k2 - 1] let value2 = nums2[j + k2 - 1] // 比较两个数组的起始坐标的值 // 如果value1小于value2 // 就舍弃nums1前i + k2部分 // 否则舍弃nums2前j + k2部分 if (value1 < value2) { return findMedianSortedArraysCore(nums1, i + k2, nums2, j, k - k2) } else { return findMedianSortedArraysCore(nums1, i, nums2, j + k2, k - k2) } }
太秀了，留下了没有技术的泪水，给我抄我都抄不会
示例 1：
nums1 = [1, 3] nums2 = [2]中位数是 2.0
示例 2：
nums1 = [1, 2] nums2 = [3, 4]中位数是(2 + 3) / 2 = 2.5
function medianNum(arr1, arr2) { let arr = [...arr1, ...arr2].sort((a,b) => a-b) let len = arr.length let index = parseInt(len/2) let num = null if (len%2 == 0) { num = (arr[index] + arr[index - 1])/2 } else { num = arr[index] }console.log(num) }
var findMedianSortedArrays = function(nums1, nums2) {
var length1 = nums1.length;
var length2 = nums2.length;
var nums3 = [];
var j = 0, k = 0;
while (j + k < (length1 + length2) / 2 + 1) {
if (nums1[j] === undefined) {
nums3.push(nums2[k++]);
} else if (nums2[k] === undefined) {
nums3.push(nums1[j++]);
} else if (nums1[j] < nums2[k]) {
nums3.push(nums1[j++]);
} else {
nums3.push(nums2[k++]);
}
}
var length3 = nums3.length;
if ((length1 + length2) % 2) {
return nums3[length3 - 2];
} else {
return (nums3[length3 - 2] + nums3[length3 - 1]) / 2;
}
};
function getMedian(m, n) {
let tempArr = [];
while (m.length && n.length) { //合并两数组
if (m[0] < n[0]) {
tempArr.push(m.shift())
} else {
tempArr.push(n.shift())
}
}
tempArr = tempArr.concat(m, n); //连接未处理的数据，获得数组合并后的所有值
let res;
let middle = (tempArr.length - 1) / 2; //中间索引位置，这里分两种情况，如果数组长度为偶数则为中间两数均值，如为奇数则为当前索引的数组元素
res = tempArr.length % 2 === 0 ? (tempArr[Math.floor(middle)] + tempArr[Math.ceil(middle)]) / 2 : tempArr[
middle];
return res;
}
console.log(getMedian([1,3,9], [3,3,5]));
// 求有序数组中位数
function fm(){
// let a1 = [1,2,3,4,5,6,7,8]
// let a2 = [9,10,11,12,13,14,15,16,17]
let a1 = [2,3,4,5,6,7]
let a2 = [1]
let k = Math.ceil((a1.length+a2.length)/2) // 9
let isOdd = (a1.length + a2.length)%2 === 1
// 求第k小的数
function fun(arr1,arr2,z){
if(z === 1){
if(isOdd){
if(!arr1.length){
return arr2[z-1]
}
if(!arr2.length){
return arr1[z-1]
}
return arr1[z-1] > arr2[z-1] ? arr2[z-1] : arr1[z-1]
}else{
if(!arr1.length){
return (arr2[z-1] + arr2[z]) / 2
}
if(!arr2.length){
return (arr1[z-1] + arr1[z]) / 2
}
let _arr = arr1.slice(0,2).concat(arr2.slice(0,2)).sort((a,b)=>{
return a - b
})
return (_arr[0] + _arr[1]) / 2
}
}
let idx = Math.floor(z/2)
if(arr1.length !== 0){
idx = arr1[idx-1] === undefined ? arr1.length : idx
}
if(arr2.length!==0 ){
idx = arr2[idx-1] === undefined ? arr2.length : idx
}
if(arr2.length===0 || arr1[idx-1] <= arr2[idx-1]){
arr1 = arr1.slice(idx)
}else{
arr2 = arr2.slice(idx)
}
z -= idx
return fun(arr1,arr2,z)
}
let res = fun(a1,a2,k)
return res
}
试了一下OK的
var findMedianSortedArrays = function (nums1, nums2) {
let i = 0, j = 0
const len = nums1.length + nums2.length
let res = []
let result = 0
while (i < nums1.length || j < nums2.length) {
if (nums1[i] && nums2[j]) {
if (nums1[i] < nums2[j]) {
res.push(nums1[i])
i++
} else if (nums1[i] >= nums2[j]) {
res.push(nums2[j])
j++
}
}
if (nums1[i] && !nums2[j]) {
res.push(nums1[i])
i++
}
if (!nums1[i] && nums2[j]) {
res.push(nums2[j])
j++
}
// 单独判断为0的情况
if (nums1[i] == 0) {
res.push(nums1[i])
i++
}
if (nums2[j] == 0) {
res.push(nums2[j])
j++
}
}
if (len % 2 == 1) {
result = res[Math.floor(len / 2)]
} else {
result = (res[len / 2 - 1] + res[len / 2]) / 2
}
return result
};
难点在于选择好排序算法