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

[lgwebdream]

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

[yuxiziyoutiankong]

 function flat(arr) {
  const l = []
  function dg (arr, p) {
    if (arr === p) return
    arr.forEach((item,index) => {
      if (item instanceof Array) {
        dg(item, arr)
      } else {
        l.push(item)
      }
    })
  }
  dg(arr)
  for(let i = 0; i < l.length; i++) {
    for(let j = i + 1; j < l.length; j++) {
      if (l[i] < l[j]) {
        let a = ''
        a = l[i]
        l[i] = l[j]
        l[j] = a
      }
    }
  }
  return l
}

[nhyu]

const fn = (arr) => [].concat(...arr).sort();
console.log(fn([[1, 3, 5], [2, 4, 6], [3, 5, 7]])); //=> [1, 2, 3, 3, 4, 5, 5, 6, 7]

[SnailOwO]

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

    // const arr1 = [1, 2, 4, 6, 9, 12, 15, 10, 3, 7, 8]

    function mergeSort(ary) {
        const len = ary.length
        if (len < 2) {
            return ary
        }
        const mid = Math.floor(len / 2)
        const left = ary.slice(0, mid)
        const right = ary.slice(mid)
        return merge(mergeSort(left), mergeSort(right))
    }

    function merge(ary1, ary2) {
        const result = []
        while (ary1.length && ary2.length) {
            if (ary1[0] <= ary2[0]) {
                result.push(ary1.shift())
            } else {
                result.push(ary2.shift())
            }
        }
        return result.concat(ary1).concat(ary2)
    }

    function flatAry(ary) {
        return Array.isArray(ary) ?
            ary.reduce((acc, cur) => [...acc, ...flatAry(cur)], []) : [ary]
    }

    // console.log(flatAry(ary))
    console.log(mergeSort(flatAry(ary)))
`

[18602435705]

/**
 * 合并两个一维有序数组
 * 双指针法
 * @param {Array} arr1
 * @param {Array} arr2
 * @returns
 */
function merge(arr1, arr2) {
  let result = [];
  let i = 0;
  let j = 0;
  for (
    let index = 0, length = arr1.length + arr2.length;
    index < length;
    index++
  ) {
    if (arr1[i] && arr2[j]) {
      if (arr1[i] <= arr2[j]) {
        result.push(arr1[i]);
        i++;
      } else {
        result.push(arr2[j]);
        j++;
      }
      continue;
    }
    if (arr1[i]) {
      result = [...result, ...arr1.slice(i)];
      break;
    }
    if (arr2[j]) {
      result = [...result, ...arr2.slice(j)];
      break;
    }
  }
  return result;
}

// 遍历二维数组，依次合并
function mergeSort(arr) {
  if (!arr.length) return [];
  let result = [];
  for (let i = 0; i < arr.length; i++) {
    result = merge(result, arr[i]);
  }
  console.log(result);
}

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

mergeSort(arr);

[18602435705]

/**
 * 合并两个一维有序数组
 * 首元素比较法
 * @param {Array} arr1
 * @param {Array} arr2
 * @returns {Array}
 */
function merge(arr1, arr2) {
  const [a, b] = [[...arr1], [...arr2]]; // 浅拷贝数组
  const result = [];
  while (a[0] && b[0]) {
    result.push(a[0] <= b[0] ? a.shift() : b.shift()); // 比较2个数组的第1个元素，谁小谁出列
  }
  return [...result, ...a, ...b];
}

// 遍历二维数组，依次合并
function mergeSort(arr) {
  if (!arr.length) return [];
  let result = [];
  for (let i = 0; i < arr.length; i++) {
    result = merge(result, arr[i]);
  }
  console.log(result);
}

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

mergeSort(arr);

[ty888]

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]]
mergeSort(arr)

[listen-amo]

简单来说，应该是归并排序少去从中分割的逻辑部分，直接进行合并排序的操作

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

console.log( merge(arr) );

function merge(arr) {
  let temp = [];
  for (let i = 0; i < arr.length; i++) {
    temp = sort(temp, arr[i]);
  }
  return temp;
}

function sort(a, b) {
  let temp = [];
  while (a.length && b.length) {
    temp.push(a[0] < b[0] ? a.shift() : b.shift());
  }
  return temp.concat(a, b);
}

[kangyana]

function flattenDeep(array, result = []) {
    array.forEach(item => {
        if (item.length) {
            flattenDeep(item, result);
        } else {
           result.push(item); 
        }
    })
    return result;
}

// 测试用例
var arr = [1, 2, [3, 4, [5, 6, 7, 3, [10, 12]], 7, 8]];
var num = flattenDeep(arr).sort((a, b) => a - b);
// => [1, 2, 3, 3, 4, 5, 6, 7, 7, 8, 10, 12]

[chenpengdepot]

function oneArry(arr){ arr=arr.flat(); arr=[...new Set(arr)].sort((a,b)=>{ return a-b }) return arr; } let oldArr=[[1,2,4],[2,3,7],[3,5,7],[4,5,8]] oldArr=oneArry(oldArr) console.log(oldArr)

[HeroTangMy]

异步解决方案 `const testAry = [ [1, 23, 45, 99], [4, 8, 9, 15, 48], [4, 8, 17, 32], [5, 7, 9] ] async function tomerge(arr1, arr2) { let mergedAry = []; // console.log(arr1,arr2) let longgerAry = arr1.length > arr2.length ? arr1 : arr2; let shortAry=arr1.length < arr2.length ? arr1 : arr2; let j = 0; let i = 0; while (shortAry.length != 0 || longgerAry.length != 0) { if (shortAry.length == 0) { mergedAry = mergedAry.concat(longgerAry) break } if (longgerAry.length == 0) { mergedAry = mergedAry.concat(shortAry) break } if (shortAry[0] > longgerAry[0]) { // console.log(mergedAry) mergedAry.push(longgerAry.shift()) } else { // console.log(mergedAry) mergedAry.push(shortAry.shift()) } } return mergedAry

}
function merge(thisary) {
    let promiseArr = []
    // console.log(thisary)
    if (thisary.length % 2 === 1) {
        thisary.push([])
    }
    return new Promise((resolve, reject) => {
        while (thisary.length >= 2) {
            // console.log(thisary[0], thisary[1])
            promiseArr.push(tomerge(thisary[0], thisary[1]))
            thisary.shift()
            thisary.shift()
        }
        console.log(promiseArr)
        Promise.all(promiseArr).then(NextNums => {
            if (NextNums.length === 1) {
                // console.log(NextNums[0])
                resolve(NextNums[0])
            } else {
                // console.log(NextNums)
                merge(NextNums).then(res => {
                    resolve(res)
                })
            }
        })
    })
}

merge(testAry).then(info => { console.log(info) })`

[wringY]

    function mergeSort(leftArr, rightArr) {

        const left = leftArr.flat(Infinity)
        const right = rightArr.flat(Infinity)

        let result = []
        let i = 0, j = 0;
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                result.push(left[i])
                i++
            } else {
                result.push(right[j])
                j++
            }
        }

        if ( i < left.length) {
            result.push(...left.slice(i))
        } else {
            result.push(...right.slice(j))
        }

        return result
    }
    console.log(mergeSort([[0, 1],[2, 3], [4, 5]], [[6, 7],[8, 9], [10, 11]]))

[nanmu-yuan]

const arr1 = [[5,9,6],[5,9,6,],[8,9,6]]; const mergeAndSex = (arr)=>[].concat(...arr).sort((a,b)=>a-b)

[AAA611]

题目应该不是要直接把数组展平然后排序，那样的话我直接：

function sortTest(nums) {
  return nums.flat().sort((a, b) => a - b)
}

题目说是归并排序的思路，归并排序分为归和并两个过程

1. 归：把数组分为若干份分别将其排为有序数组
2. 并：把有序数组进行合并成为最终的排序结果

题目中给出的是多个有序数组，需要合并为一个有序数组，因此不需要“归”，直接“并”

function sort(nums) {
  let leftNums = nums[0]
  let res
  for (let i = 1; i < nums.length; i++) {
    res = []
    let rightNums = nums[i]
    let left = 0
    let right = 0
    while (left < leftNums.length && right < rightNums.length) {
      if (leftNums[left] < rightNums[right]) {
        res.push(leftNums[left])
        left++
      } else {
        res.push(rightNums[right])
        right++
      }
    }
    if (left < leftNums.length) {
      res.push(...leftNums.slice(left))
    }
    if (right < rightNums.length) {
      res.push(...rightNums.slice(right))
    }
    leftNums = res.slice()
  }
  return res
}

[jakenik]

const mergeList = (...list) => { return list.flat(Infinity).sort((a, b) => a - b) }

[aaronxdd]

const myFlatSort = (arr) => { if (!Array.isArray(arr)) return; return arr.flat().sort(); }