腾讯：数组扁平化、去重、排序

关于 Array 的属性、方法这里不再做介绍，详看 MDN Array 。

面试题：

已知如下数组：var arr = [ [1, 2, 2], [3, 4, 5, 5], [6, 7, 8, 9, [11, 12, [12, 13, [14] ] ] ], 10];

编写一个程序将数组扁平化去并除其中重复部分数据，最终得到一个升序且不重复的数组

答案：

// 扁平化
const flattenDeep = (array) => array.flat(Infinity)

// 去重
const unique = (array) => Array.from(new Set(array))

// 排序
const sort = (array) => array.sort((a, b) => a-b)

// 函数组合
const compose = (...fns) => (initValue) => fns.reduceRight((y, fn) => fn(y), initValue)

// 组合后函数
const flatten_unique_sort = compose( sort, unique, flattenDeep)

// 测试
var arr = [ [1, 2, 2], [3, 4, 5, 5], [6, 7, 8, 9, [11, 12, [12, 13, [14] ] ] ], 10]
console.log(flatten_unique_sort(arr))
// [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]

可结合携程&蘑菇街&bilibili：手写数组去重、扁平化函数查看

补充：flat() 方法对node版本有要求，至少需要12.0以上，不知道的小伙伴会搞错，然后我的方法是
通过array.some() + concat来实现这个flat()，这个对node版本的限制比较低，可行性较高。。
源码：

let arr =[[1, 2, 2], [3, 4, 5, 5], [6, 7, 8, 9, [11, 12, [12, 13, [14]]]], 10]
function newArray ( ) {
  while(arr.some(Array.isArray)){
    arr = [].concat(...arr)
  }
  arr = [...new Set(arr)].sort((a,b)=>{
    return a-b
  })
  return arr
}
newArray()
console.log(arr);

给个递归方法：

const ans = [];
var flaten = function (nums) {
    if (typeof nums == 'number') {
        return nums;
    } // 出口
    nums.forEach(element => {
        let tmp = flaten(element);
        if (tmp != null) {
            ans.push(tmp);
        }
    });
}

ans是作为全局变量的，也可以作为参数传递。
这题的难点在于拍平数组，之后的去重可以用set，也可以用map，甚至可以用数组，排序可以自己写或者sort。

function insertion(arr){
    return arr.flat(Infinity).reduce((pre,cur)=>{
        return !pre.includes(cur)?pre.concat(cur):pre
    },[]).sort((a,b)=>a-b)
}

const getArray = (arr, dep) => Array.from(new Set(arr.flat(dep))).sort()

考虑到这儿有三个步骤，可以用函数组合compose来把这三个函数组合在一起。
参考数组去重：mqyqingfeng/Blog#27
参考redux的函数组合： https://github.com/reduxjs/redux/blob/master/src/compose.ts

\\ 数组扁平化
var _flatten = function (array) {
  return array.reduce(function (prev, next) {
    return prev.concat(Array.isArray(next) ? _flatten(next) : next)
  }, [])
}
\\ 数组去重
var _unique = function (array) {
  var map = {}
  return array.filter(function (item, index, array) { // 用typeof item +JSON.stringfy(item)的原因是用来区分两个对象
    return map.hasOwnProperty(typeof item + JSON.stringify(item)) ? false : map[typeof item + JSON.stringify(item)] = true
  })
}
\\ 数组排序
var _sort = function (array) {return array.sort((a, b) => a - b)}
\\ 函数组合
var compose = (...fns) => (initValue) => fns.reduceRight((y, fn) => fn(y), initValue)

var flatten_unique_sort = compose( _sort, _unique, _flatten)
var array = [ [1, 2, 2], [3, 4, 5, 5], [6, 7, 8, 9, [11, 12, [12, 13, [14] ] ] ], 10]
console.log(flatten_unique_sort(array))

const getArray = (arr, dep) => Array.from(new Set(arr.flat(dep))).sort()

This looks so cool！But，it has a mistake。

const getArray = (arr, dep) => Array.from(new Set(arr.flat(dep))).sort((a,b) => a-b);

/**
 * 数组扁平化、去重、排序
 */
const list = [1, [2, 3, 8], [3, 6, 4], [5, [6, 7, [8, 1, 2]]]];

/* ====== 扁平化 ====== */
function flat(arr) {
  return arr.reduce((acc, cur) => {
    acc = acc.concat(Array.isArray(cur) ? flat(cur) : cur);
    return acc;
  }, []);
}

/* ====== 数组去重 ====== */
function unique(arr) {
  return arr.reduce((acc, cur) => {
    if (!acc.includes(cur)) acc.push(cur);
    return acc;
  }, []);
}

/* ====== 排序 ====== */
// 冒泡排序
function pupleSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i; j < arr.length; j++) {
      if (arr[i] > arr[j]) {
        const temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
      }
    }
  }
  return arr;
}

// 快速排序1
function quickSort(arr) {
  if (arr.length <= 1) return arr;
  const left = [];
  const right = [];
  const mid = arr.shift(arr);

  arr.forEach((item) => {
    if (item <= mid) left.push(item);
    else right.push(item);
  });

  return quickSort(left).concat(mid).concat(quickSort(right));
}

const flatArr = flat(list);
console.log('flatArr: ', flatArr); // [1, 2, 3, 8, 3, 6, 4, 5, 6, 7, 8, 1, 2]

const uniArr = unique(flatArr);
console.log('uniArr: ', uniArr); // [1, 2, 3, 8, 6, 4, 5, 7]

// const sortArr = pupleSort(uniArr); // [1, 2, 3, 4, 5, 6, 7, 8]
const sortArr = quickSort(uniArr); // [1, 2, 3, 4, 5, 6, 7, 8]

console.log('sortArr: ', sortArr);

const getArray = (arr, dep) => Array.from(new Set(arr.flat(dep))).sort()
This looks so cool！But，it has a mistake。

const getArray = (arr, dep) => Array.from(new Set(arr.flat(dep))).sort((a,b) => a-b);

it works well for me .

[2,6,4,8,1].sort()
// (5) [1, 2, 4, 6, 8]

const getArray = (arr, dep) => Array.from(new Set(arr.flat(dep))).sort()
This looks so cool！But，it has a mistake。
const getArray = (arr, dep) => Array.from(new Set(arr.flat(dep))).sort((a,b) => a-b);
it works well for me .
[2,6,4,8,1].sort()
// (5) [1, 2, 4, 6, 8]

直接为sort()是根据Unicode来排序的

let array = [ [1, 2, 2], [3, 4, 5, 5], [6, 7, 8, 9, [11, 12, [12, 13, [14] ] ] ], 10]
// 转成字符串
let flatArr = array.toString(); //输出 "1,2,2,3,4,5,5,6,7,8,9,11,12,12,13,14,10"
// 去重、转成数组
let disArr = Array.from(new Set(flatArr.split(',')))
//排序
let result = disArr.sort((a,b) => a-b);
console.log(result)
// 输出 ["1", "2", "3", "4", "5", "6", "7", "8", "9", "10", "11", "12", "13", "14"]

var arr = [[1,2,2],[3,4,5,5],[6,7,8,9,[11,12,[12,13,[14]]]],10]
function flat (arr){
while(arr.some(it => Array.isArray(it))){
arr = [].concat(...arr)
}
arr = [...new Set(arr)].sort((a,b) => a - b)
return arr
}

console.log(flat(arr))

var arr = [[1, 2, 2], [3, 4, 5, 5], [6, 7, 8, 9, [11, 12, [12, 13, [14]]]], 10];

/**
 * 展平数组
 * @param {number[]} array
 */
function flatten(array) {
  let temp = array;
  while (temp.some(Array.isArray)) {
    temp = [].concat(...temp);
  }
  return temp;
}

/**
 * 计数排序加去重
 * @param {number[]} array
 */
function countSort(array) {
  const max = Math.max.apply(null, array);
  const min = Math.min.apply(null, array);
  const d = max - min;
  const countArray = Array(d + 1).fill(0);
  array.forEach((num) => {
    countArray[num - min]++;
  });

  return countArray.reduce((sorted, current, index) => {
    if (current > 0) {
      sorted.push(index + min);
    }
    return sorted;
  }, []);
}

function sort(array) {
  let temp = flatten(array);
  return countSort(temp);
}

const res = sort(arr);
console.log(res);
// [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14];

//  数组扁平化
const flatten = (array) =>
  array.reduce(
    (prev, next) => prev.concat(Array.isArray(next) ? flatten(next) : next),
    []
  )

// 数组去重
var unique = (array) =>
  array.filter((item) =>
    unique[uniqueKey(item)]
      ? false
      : (unique[uniqueKey(item)] = true)
  )

// uniqueKey  的值跟传入的 item 有关


// 数组排序
var sort = array => array.sort((a, b) => a - b)

// 函数组合
var compose = (...fns) => (...args) => fns.reduce((p, n) => n(p), args)

var flatten_unique_sort = compose( flatten, unique, sort )
var array = [ [1, 2, 2], [3, 4, 5, 5], [6, 7, 8, 9, [11, 12, [12, 13, [14] ] ] ], 10]
console.log(flatten_unique_sort(array))

let arr =[[1, 2, 2], [3, 4, 5, 5], [6, 7, 8, 9, [11, 12, [12, 13, [14]]]], 10]
let list = [];
function flat(arr) {
    for (const item of arr) {
        if (Array.isArray(item)) {
            flat(item);
        }
        else {
            let index = repeat(item);
            if (index === -2) {
                continue;
            }
            else if (index === 0) {
                list.push(item);
            }
            else if (index === -1) {
                list.splice(0, 0, item);
            }
            else {
                list.splice(index, 0, item);
            }
        }
    }
}

function repeat(data) {
    if (list.length === 1) {
        return data === list[0] ? -2 : data > list[0] ? 1 : 0;
    }
    for(let i = 0; i < list.length - 1; i++) {
        let prev = list[i];
        let post = list[i + 1];
        if (data === prev || data === post) {
            return -2;
        }
        else if (data < prev) {
            return i - 1;
        }
        else if (data > prev && data < post) {
            return i + 1;
        }
        else {
            continue;
        }
    }
    return 0;
}

flat(arr);
console.log(list);

const flattenUniqueSort = (array) => {
  //  拍平
  const flatten = (array) => {
    return array.reduce((result, it) => {
      return result.concat(Array.isArray(it) ? flatten(it) : it)
    }, [])
  }
  // 去重
  const unique = (array) => [ ...new Set(array) ]
  // 排序
  const sort = (array) => array.sort((a, b) => a - b)

  return sort(unique(flatten(array)))
}

function flat(arr){
 return [...new Set(arr.toString().split(",").map(Number).sort((a,b)=>a-b))]
}

var arr = [ [1, 2, 2], [3, 4, 5, 5], [6, 7, 8, 9, [11, 12, [12, 13, [14] ] ] ], 10]; // 将数组使用toString() 将数组进行扁平化(字符串) // 将扁平化的字符串变成字符串数组然后将字符串数组内的数据进行所有的转变最后进行排序 var arrStr = arr.toString().split(',').map(Number).sort((a,b)=>a-b) console.log('arrStr',arrStr)

给个递归方法：
const ans = [];
var flaten = function (nums) {
    if (typeof nums == 'number') {
        return nums;
    } // 出口
    nums.forEach(element => {
        let tmp = flaten(element);
        if (tmp != null) {
            ans.push(tmp);
        }
    });
}
ans是作为全局变量的，也可以作为参数传递。
这题的难点在于拍平数组，之后的去重可以用set，也可以用map，甚至可以用数组，排序可以自己写或者sort。

这样会不会更好
const arr = [1, [1,2], [1,2,3]]
function flat(arr) {
let result = []
for (const item of arr) {
item instanceof Array ? result = result.concat(flat(item)) : result.push(item)
}
return result
}

flat(arr) // [1, 1, 2, 1, 2, 3]

function translateArr(arr) {
    while(arr.some(Array.isArray)) {
        arr = [].concat(...arr)
    }
    
    arr = [...new Set(arr)]
    arr = arr.sort((a,b)=>a-b)
    return arr
}

let arrE = flatArr([1,2,3,[4,1,2, 9,0],[1,2,[1,4,5, [3,5,6]]]])

var arr = [[1, 2, 3], [2, 3, 4, 4, 45, 5], [6, 7, 8, 5]]
function flatern1(arr = []) {
    //利用toString的性质
    let setArry = new Set(arr.toString().split(',').sort((a, b) => a - b))
    return Array.from(setArry).map((value) => Number.parseInt(value))
}
//flat() 方法会按照一个可指定的深度递归遍历数组，并将所有元素与遍历到的子数组中的元素合并为一个新数组返回。
function flatern2(arr) {
    return Array.from(new Set(arr.flat(4))).sort((a, b) => a - b)
}
console.log(flatern1(arr));
console.log(flatern2(arr));

回字的四种写法

// 扁平化 第一种
const flatten = (target) => {
  if (Array.isArray(target)) {
    return target.flat(Infinity);
  }
};


// 扁平化 第二种
const flatten_0 = (target) => {
  if (Array.isArray(target)) {
    return target
      .toString()
      .split(",")
      .map((ele) => Number(ele));
  }
};

// 扁平化 第三种
const flatten_1 = (target, arrs) => {
  arrs = arrs || [];
  target.forEach((element) =>
    Array.isArray(element) ? flatten_1(element, arrs) : arrs.push(element)
  );
  return arrs;
};

// 扁平化 第四种
const flatten_3 = (target) => {
  if(Array.isArray(target)){
    return target.reduce((add, ele)=>{
      return add.concat(Array.isArray(ele) ? flatten_3(ele):ele)
  }, [])
  }
}

这是来自QQ邮箱的假期自动回复邮件。你好，我最近正在休假中，无法亲自回复你的邮件。我将在假期结束后，尽快给你回复。

Navigation Menu

Repository navigation

腾讯：数组扁平化、去重、排序 #5

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

腾讯：数组扁平化、去重、排序 #5

Description

Activity

352800205 commented on Apr 3, 2020

ai977313677 commented on Apr 6, 2020

lyllovelemon commented on Apr 8, 2020

diveDylan commented on Apr 22, 2020

Aiyoweioo commented on Apr 26, 2020

sfsoul commented on Apr 27, 2020

zero9527 commented on Apr 28, 2020

diveDylan commented on Apr 28, 2020

sfsoul commented on Apr 28, 2020

plane-hjh commented on Apr 28, 2020

Yin-fujun commented on May 14, 2020

zhangkaivictor commented on Jun 17, 2020

zhangkaivictor commented on Jun 17, 2020

xblj commented on Jul 9, 2020

Been101 commented on Jul 11, 2020

hejunjieGitHub commented on Jul 30, 2020

qianlongo commented on Aug 15, 2020

njueyupeng commented on Aug 17, 2020

yucheng-yc commented on Nov 18, 2020

huohuoit commented on Apr 19, 2021

Baymaxxx commented on May 30, 2021

sionnigjt commented on Oct 23, 2021

xiaochengzi6 commented on May 14, 2022

lyllovelemon commented on May 14, 2022

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions