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

Question

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

sisterAn opened this issue 4 years ago · 24 comments

关于 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：手写数组去重、扁平化函数查看

Answer 1 · 2020-04-03T04:31:40.000Z

补充：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);

Answer 2 · 2020-04-06T02:27:52.000Z

给个递归方法：

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。

Answer 3 · 2020-04-08T07:53:25.000Z

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

Answer 4 · 2020-04-22T14:38:45.000Z

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

Answer 5 · 2020-04-26T11:53:09.000Z

考虑到这儿有三个步骤，可以用函数组合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))

Answer 6 · 2020-04-27T12:16:51.000Z

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);

Answer 7 · 2020-04-28T08:17:45.000Z

/**
 * 数组扁平化、去重、排序
 */
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);

Answer 8 · 2020-04-28T11:03:58.000Z

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]

Answer 9 · 2020-04-28T11:21:56.000Z

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]

Answer 10 · 2020-04-28T13:17:05.000Z

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来排序的

Answer 11 · 2020-05-14T06:32:11.000Z

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"]

Answer 12 · 2020-06-17T03:20:08.000Z

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))

Answer 13 · 2020-06-17T03:45:15.000Z

zhangkaivictor commented 4 years ago

Answer 14 · 2020-07-09T09:09:41.000Z

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];

Answer 15 · 2020-07-11T09:53:09.000Z

//  数组扁平化
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))

Answer 16 · 2020-07-30T12:09:54.000Z

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);

Answer 17 · 2020-08-15T03:32:35.000Z

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)))
}

Answer 18 · 2020-08-17T11:29:47.000Z

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

Answer 19 · 2020-11-18T14:09:55.000Z

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)

Answer 20 · 2021-04-19T08:09:00.000Z

给个递归方法：
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]

Answer 21 · 2021-05-30T03:54:27.000Z

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]]]])

Answer 22 · 2021-10-23T12:36:12.000Z

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));

Answer 23 · 2022-05-14T04:34:54.000Z

回字的四种写法

// 扁平化 第一种
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)
  }, [])
  }
}

Answer 24 · 2022-05-14T04:35:20.000Z

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