第 2 题：合并二维有序数组成一维有序数组，归并排序的思路

[lgwebdream]

trafficstars

欢迎在下方发表您的优质见解

[Genzhen]

function mergeSort(arr) {
    const len = arr.length
    // 处理边界情况
    if(len <= 1) {
        return arr[0]
    }   
    // 计算分割点
    const mid = Math.floor(len / 2)    
    // 递归分割左子数组，然后合并为有序数组
    const leftArr = mergeSort(arr.slice(0, mid)) 
    // 递归分割右子数组，然后合并为有序数组
    const rightArr = mergeSort(arr.slice(mid,len))  
    // 合并左右两个有序数组
    arr = mergeArr(leftArr, rightArr)  
    // 返回合并后的结果
    return arr
}
  
function mergeArr(arr1, arr2) {  
    // 初始化两个指针，分别指向 arr1 和 arr2
    let i = 0, j = 0   
    // 初始化结果数组
    const res = []    
    // 缓存arr1的长度
    const len1 = arr1.length  
    // 缓存arr2的长度
    const len2 = arr2.length  
    // 合并两个子数组
    while(i < len1 && j < len2) {
        if(arr1[i] < arr2[j]) {
            res.push(arr1[i])
            i++
        } else {
            res.push(arr2[j])
            j++
        }
    }
    // 若其中一个子数组首先被合并完全，则直接拼接另一个子数组的剩余部分
    if(i<len1) {
        return res.concat(arr1.slice(i))
    } else {
        return res.concat(arr2.slice(j))
    }
}

var arr=[[1,2,4],[2,3,7],[3,5,7],[4,5,8]]
mergeArr(arr)

[Genzhen]

/**
 * 解题思路：
 * 双指针 从头到尾比较 两个数组的第一个值，根据值的大小依次插入到新的数组中
 * 空间复杂度：O(m + n)
 * 时间复杂度：O(m + n)
 * @param {Array} arr1
 * @param {Array} arr2
 */

function　merge(arr1, arr2){
    var　result=[];
    while(arr1.length>0 && arr2.length>0){
        if(arr1[0]<arr2[0]){
              /*shift()方法用于把数组的第一个元素从其中删除，并返回第一个元素的值。*/
            result.push(arr1.shift());
        }else{
            result.push(arr2.shift());
        }
    }
    return　result.concat(arr1).concat(arr2);
}

function mergeSort(arr){
    let lengthArr = arr.length;
    if(lengthArr === 0){
     return [];
    }
    while(arr.length > 1){
     let arrayItem1 = arr.shift();
     let arrayItem2 = arr.shift();
     let mergeArr = merge(arrayItem1, arrayItem2);
     arr.push(mergeArr);
    }
    return arr[0];
}
let arr1 = [[1,2,3],[4,5,6],[7,8,9],[1,2,3],[4,5,6]];
let arr2 = [[1,4,6],[7,8,10],[2,6,9],[3,7,13],[1,5,12]];
mergeSort(arr1);
mergeSort(arr2);

[Genzhen]

// 方法1：使用concat
const flatten1 = (arr) => {
while (arr.some((item) => Array.isArray(item))) {
    arr = [].concat(...arr);
}
return arr;
};
// 方法2：使用reduce
const flatten2 = (arr) =>
arr.reduce(
    (acc, cur) =>
    Array.isArray(cur) ? [...acc, ...flatten2(cur)] : [...acc, cur],
    []
);
// test
var arr = [1, 2, [3, 4, [5, 6], 7, 8]];
console.log(flatten1(arr));
console.log(flatten2(arr));

[hehuilin]

function sortFlatArray (arr) {
		function flatArray (arr) {
			const newArr = arr.flat()
			return newArr.some(item => Array.isArray(item))? flatArray(newArr) : newArr
		}
		if (!arr || !arr.length) {
			return []
		}
		let flattenedArr = flatArray(arr)
		return flattenedArr.sort((a, b) => {
			return a - b
		})
	}

[hehuilin]

// 方法1：使用concat
const flatten1 = (arr) => {
while (arr.some((item) => Array.isArray(item))) {
    arr = [].concat(...arr);
}
return arr;
};
// 方法2：使用reduce
const flatten2 = (arr) =>
arr.reduce(
    (acc, cur) =>
    Array.isArray(cur) ? [...acc, ...flatten2(cur)] : [...acc, cur],
    []
);
// test
var arr = [1, 2, [3, 4, [5, 6], 7, 8]];
console.log(flatten1(arr));
console.log(flatten2(arr));

这个是不是少了排序的功能，只做了将多维数组转换为一维数组

[hehuilin]

function sortFlatArray (arr) { function flatArray (arr) { const newArr = arr.flat() return newArr.some(item => Array.isArray(item))? flatArray(newArr) : newArr } if (!arr || !arr.length) { return [] } let flattenedArr = flatArray(arr) return flattenedArr.sort((a, b) => { return a - b }) }

数据长度的判断逻辑放在函数最开始是不是更好一点？

我是放在前面了呀，不知道你说的意思是要？

[SiHao24]

function sortFlatArray (arr) { function flatArray (arr) { const newArr = arr.flat() return newArr.some(item => Array.isArray(item))? flatArray(newArr) : newArr } if (!arr || !arr.length) { return [] } let flattenedArr = flatArray(arr) return flattenedArr.sort((a, b) => { return a - b }) }

数据长度的判断逻辑放在函数最开始是不是更好一点？

我是放在前面了呀，不知道你说的意思是要？

看错了，不好意思。

[123456zzz]

const mergeSort = (arr1: number[], arr2: number[]) => {
  const len1 = arr1.length,
    len2 = arr2.length;
  let i = 0,
    j = 0,
    arr = [];
  if (len1 === 0) return arr2;
  if (len2 === 0) return arr1;
  while (i < len1 || j < len2) {
    if (arr1[i] <= arr2[j] || j === len2) {
      arr.push(arr1[i]);
      i++;
    } else {
      arr.push(arr2[j]);
      j++;
    }
  }
  return arr;
};

//test

const arr1 = [1, 2, 3];
const arr2 = [2, 3, 4];
const arr3 = [1, 5, 6];

const arr = [arr1, arr2, arr3];

const res = arr.reduce((pre, cur) => mergeSort(pre, cur), []);

console.log(res);

[ppmiao0628]

[[1,2,3],[4,5,6],[7,8,9],[1,2,3],[4,5,6]].flat(Infinity).sort((a,b)=>{ return a-b;})

[ppoollaarr]

function merge(left: number[], right: number[]): number[] {

    let result: number[] = [];
    while (left.length > 0 && right.length > 0) {
        if (left[0] <= right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }
    while (left.length > 0) {
        result.push(left.shift());
    }
    while (right.length > 0) {
        result.push(right.shift());
    }
    return result;
}

[chengming9731]

function merge (arr) {
      if (arr.length === 0) {
         return []
      }
      // 扁平化数组
      let newArr = arr.flat(Infinity)
      // 排序
      return newArr.sort(($1, $2) => $1 - $2)
   }
   merge([[1,2,3],[4,5,6],[7,8,9],[1,2,3],[4,5,6]])

不知道怎么调整格式凑合一下-_-

[work25]

let a = [1, 2, [3, 4, [5, 6]]]
let arr = []

function change(a) {
    a.forEach(item => {
        if (typeof item == 'object') {
            change(item)
        } else {
            arr.push(item)
        }
    })
}
change(a)
arr = arr.sort()

[HuberTRoy]

let tt = [
    [1,2,3,4,5],
    [8,9,10],
    [6,8,9],
]

function sort(arr) {
    if (!(arr instanceof Array)) {
        return
    }

    // 这里还应该有一个非 二维数组的判断。

    return arr.flat().sort((a, b) => {
        if (typeof(a) !== 'number' || typeof(a) !== 'bigint') {
            throw Error('Number need')
        }

        if (typeof(b) !== 'number' || typeof(b) !== 'bigint') {
            throw Error('Number need')
        }

        return a - b 
    })
}

console.log(sort(tt))

[523451928]

function flat(arr) {
  let copyArr = [...arr]
  while (copyArr.some(item => Array.isArray(item))) {
    copyArr = [].concat(...copyArr)
  }
  return copyArr.sort((a, b) => { a - b })
}
flat([[1, 2], [6, 4, 2], [3]])

[GolderBrother]

function flattenAndSort(arr = []) { // 方法一: 借助concat方法 // function flatten(arr) { // while (arr.some((item) => Array.isArray(item))) { // arr = [].concat(...arr); // } // return arr; // }

// 方法二: 借助reduce方法 // function flatten(arr = []) { // return arr.reduce((accu, current) => { // return Array.isArray(current) // ? [...accu, ...flatten(current)] // : [...accu, current]; // }, []); // }

// 方法三: 直接使用数组的API flat, 传入Infinity值 function flatten(arr = []) { return arr.flat(Infinity); }

// 排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。 // 归并排序采用的是分治思想。 function mergeSort(arr = []) { // 采用自上而下的递归方法 const len = arr.length; if (len < 2) return arr; const middleIndex = len >> 1, left = arr.slice(0, middleIndex), right = arr.slice(middleIndex); // 开局就深度递归到子元素,然后再两两元素比较排序 return merge(mergeSort(left), mergeSort(right)); } function merge(left = [], right = []) { const result = []; while (left.length && right.length) { if (left[0] <= right[0]) { // 类似队列的队首出队 result.push(left.shift()); } else { result.push(right.shift()); } } // 如果还有剩余的元素，直接从头到尾放到数组尾部 while (left.length) result.push(left.shift()); while (right.length) result.push(right.shift()); return result; }

return mergeSort(flatten(arr)); }

let arr = [ [1, 4, 6], [7, 8, 10], [2, 6, 9], [3, 7, 13], [1, 5, 12], ]; console.log(flattenAndSort(arr));

[JJL-SH]

const mergeSort = (arr) => arr.reduce((cacheArr, it) => [...cacheArr, ...it], []).sort((a, b) => a - b); const arr = [[1, 2, 3], [6], [7, 8, 9], [1, 12, 13], [4, 5, 6]]; mergeSort(arr)

[huzedong2015]

const data = [
    [6, 7, 8, 9],
    [1, 2, 3, 4, 5],
    [10, 11, 12, 13]
];

const newData = data.flat();

newData.sort((a, b) => a - b);

如果是上面这种数据，可以先排序再扁平化数组

[Leolijiaming]

type flatReturn = Array;

export const flat = ( a: Array ): flatReturn => {

const newArr = a.toString().split(",");

return newArr.sort((a, b) => a - b);

} //test flat([[1, 2], [6, 4, 2], [3]])

[WJiaoJiao]

let arr = [[7,8,9],[1,2,3],[4,5,6]];

function mergeSort(arr) {
    let len = arr.length;
    if(len <= 1) return arr[0];
    let middleNum = Math.floor(len / 2);
    let left = arr.slice(0, middleNum);
    let right = arr.slice(middleNum);
    return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
    let result = [];
    while(left.length > 0 && right.length > 0) {
        if(left[0] < right[0]) {
            result.push(left.shift())
        }else {
            result.push(right.shift())
        }
    }
    while(left.length > 0) {
        result.push(left.shift());
    }
    while(right.length > 0) {
        result.push(right.shift());
    }
    return result;
}

mergeSort(arr);

[gejianvs]

// 思路： 首先扁平化数组，再进行排序， 扁平化可以通过数组的tostring 和字符串split 方法 const arr =[[1,2,4],[2,3,7],[3,5,7],[4,5,8]] const mySort = arr2 =>{ if(Array.isArray(arr2)){ const plantArr = arr2.toString().split(',') plantArr.sort((a, b)=> a-b) return plantArr } return [] }

console.log(mySort(arr))

[qiheng]

function mergeSort(arr) {

	let result = [];

	if (Array.isArray(arr)) {

		let newArr = JSON.parse(JSON.stringify(arr))

		while(newArr.length > 0) {

			let arrTmp = newArr.shift();

			result = result.concat(arrTmp)
			
		}

		result.sort(function(v1,v2) {
			return v1-v2
		})

	}

	return result

}

var arr = [[1,2,3],[4,5,6],[7,8,9],[1,2,3,21,45,33],[4,5,6]];

mergeSort(arr)

[noney]

/**
 * [mergeArrAndSort description]
 * @param  {Array}  arr    [二维数组]
 * @param  {Array}  resArr [结果数组]
 * @return {[type]}        [description]
 */
function mergeArrAndSort(arr = [], resArr = []) {
  for(let v of arr) {
    if (Array.isArray(v)) {
      mergeArrAndSort(v, resArr);
    } else {
      resArr.push(v);
    }
  }
  console.log(resArr.sort());
  return resArr.sort();
}

mergeArrAndSort([[1, 2], [2, 3], [4, 5, 7]]);
mergeArrAndSort([[1, 2], [2, 3], [4, 5, [6, 7, 8]]]);

[ruandao]

const mergeSort = (a: Array<number>, b: Array<number>): Array<number> => {
    if(a.length === 0) {
        return a
    }
    if(b.length === 0) {
        return b
    }
    const arr = [];
    let ai=0;
    let bi = 0;
    while(ai < a.length && bi < b.length) {
        if(a[ai] < b[bi]) {
            arr.push(a[ai]);
            ai++;
        } else {
            arr.push(b[bi]);
            bi++;
        }
    }
    for(;ai<a.length;ai++) {
        arr.push(a[ai])
    }
    for(;bi<b.length;bi++) {
        arr.push(b[bi])
    }
    return arr;
}
// 好吧，看错了....
const mergeSortArr = (arr: Array<number[]>): Array<number> => {
    if(!Array.isArray(arr)) {
        throw "传入的不是数组"
    }

    if(arr.length === 0) {
        throw "数组中至少需要一个元素"
    }
    if(arr.length === 1) {
        return arr[0];
    }
    return arr.slice(1).reduce((acc, item) => mergeSort(acc, item), arr[0])
}

var arr = [[1,2,3],[4,5,6],[7,8,9],[1,2,3,21,33, 45],[4,5,6]];

const result = mergeSortArr(arr)
console.log(result)

[chengazhen]

没有添加任何判断只是为了实现需求 不知道自己写的对不对 看上面大家都写了好多 是不是我理解错了啊

• 先利用flat进行扁平化处理
• 然后利用Set对象进行去重处理
• 利用from将set数组化
• 最后利用sort排序

 let arr = [
      [1, 4, 6],
      [7, 8, 10],
      [2, 6, 9],
      [3, 7, 13],
      [1, 5, 12]
    ];
//[[1,2,3],[4,5,6],[7,8,9],[1,2,3],[4,5,6]]

    function func(arr) {
      return Array.from(new Set(arr.flat(1))).sort((a, b) => a - b)
    }

//[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13]
// [1, 2, 3, 4, 5, 6, 7, 8, 9]

[markduan]

const arrayA = [1,3,5,7,9];
const arrayB = [111,221,331,441,551,661,771,881,991];
const arrayC = [2,4,5,6,8,10];
const arrayD = [11,22,33,44,55,66,77,88,99];
const matrix = [arrayA, arrayB, arrayC, arrayD]

function mergeArray(arrayA, arrayB) {
  let i = j = 0;
  const sortedArray = [];

  while(i < arrayA.length && j < arrayB.length) {
    if (arrayA[i] < arrayB[j]) {
      sortedArray.push(arrayA[i]);
      i += 1;
      continue
    }

    sortedArray.push(arrayB[j]);
    j += 1;
  }

  sortedArray.push(...arrayA.slice(i));
  sortedArray.push(...arrayB.slice(j));

  return sortedArray;
}

function flatMatrix(matrix) {
  return matrix.reduce((arrayA, arrayB) => {
    return mergeArray(arrayA, arrayB);
  });
}

console.log(flatMatrix(matrix));

[jieceng]

function mergeArray(arr){ return Array.prototype.concat.apply([],arr).sort() } let arr = [[1,2,3],[4,5,6],[7,8,9],[1,2,3],[4,5,6]]; console.log( mergeArray(arr) )

[lin09]

import _ from 'lodash' console.log(.orderBy(.flatten(arr)))

[Cabzer-x]

let a = [[1,2,3],[1,1,2],[2,3,4]] let arr = a.reduce((prev,cur) => { return prev.concat(cur) },[]).sort((a,b) => { return a - b; })

[lion1ou]

function mergeArr(Arr) {
  function isArr(arr) {
    return Object.prototype.toString.call(arr) === "[object Array]";
  }
  if (!isArr(Arr)) {
    throw new Error("参数必须是数组");
  } else {
    if (Arr.length === 0 || !isArr(Arr[0])) {
      throw new Error("参数必须是二维数组");
    }
  }
  function sortMerge(Arr1, Arr2) {
    let i = 0;
    let j = 0;
    let result = [];
    if (Arr1.length === 0 || Arr2.length === 0) {
      return [...Arr1, ...Arr2];
    }
    while (i < Arr1.length || j < Arr2.length) {
      if (Arr1[i] < Arr2[j]) {
        result.push(Arr1[i]);
        i++;
      }
      if (Arr1[i] > Arr2[j]) {
        result.push(Arr2[j]);
        j++;
      }
      if (Arr1[i] === Arr2[j]) {
        result.push(Arr1[i]);
        i++;
        result.push(Arr2[j]);
        j++;
      }
      if (Arr1[i] === undefined && Arr2[j] !== undefined) {
        result.push(Arr2[j]);
        j++;
      }
      if (Arr1[i] !== undefined && Arr2[j] === undefined) {
        result.push(Arr1[i]);
        i++;
      }
    }
    return result;
  }
  return Arr.reduce((res, item) => {
    return sortMerge(res, item);
  }, []);
}

// 测试代码

var arr = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9],
  [1, 2, 3, 21, 33, 45],
  [4, 5, 6],
];

var arr1 = [
  [1, 2, 4],
  [2, 3, 7],
  [3, 5, 7],
  [4, 5, 8],
];


console.log("result:", mergeArr(arr));
console.log("result:", mergeArr(arr1));

[qinchao888]

function mergeSort(arr) {
  let left = arr.shift()
  let res = left
  while(arr.length) {
    let right = arr.shift()
    res = merge(res, right)
  }
  return res
}

function merge (left, right) { // 归并排序
  let i = 0, j = 0
  let res = []
  while(i < left.length && j < right.length) {
    if (left[i] < right[j]) {
      res.push(left[i])
      i++
    } else {
      res.push(right[j])
      j++
    }
  }
  while(i < left.length) {
    res.push(left[i])
    i++
  }
  while(j < right.length) {
    res.push(right[j])
    j++
  }
  return res
}
console.log(merge([1, 3, 5], [2, 3, 4, 8]))