数组类高频面试题

一.数组扁平化(5种解法)

拍平多维数组var arr = [1, 2, 3, [3, 3, 3, [5, 4, 5, 6, 6, 7, 8]],333, 4444]];

• 递归处理
• 闭包+递归处理
• es6扩展运算符+reduce/concat+push+reduce
• toString处理
• rest参数

1. 递归处理

function flatten(arr){
  let child = []; //child变量在每次递归时都会清空。故每次遍历结束都需要返回
  for(let i of arr){
    if(Array.isArray(i)){
      child = [...child, ...flatten(i)] 
      //注意：flatten(i)之后的结果也需要展开，否则，只能复制数组，无法扁平化
    }else{
      child = [...child, i]
    }
  }
  return child;
}
function flatten(arr){
  let child = []
  for(let item of arr){
    if(Array.isArray(item)){  
      child = child.concat(flatten(item))
    }else{
      child.push(item)
    }
  }
  return child
}
console.log(flatten(arr))
//  concat方法不会改变原数组，join会
//  concat连接的不仅可以是具体的值，也可以是数组，当是数组时，添加的时数组中的值，该方法不改变原数组，而是返回一个连接后的副本，故使用concat,要把结果赋值给新变量
//  push会改写原数组，并返回新数组的长度，故不需要新变量承接

2. 闭包+递归处理

let product = () => {
  let child = [] //闭包中的child变量会一直在内存中，是一个累积变量
  let flatten = (arr) => {
    for(let item of arr){
      if(Array.isArray(item)){
        flatten(item) //此处的作用只是判断item为数组，就将它推入下一次递归
      }else{
        child.push(item) 
        //push会改变原数组，并返回新数组的长度，所有的数组元素都是在此处被push进child变量
      }
    }
    return child //每次都返回一个累积后的child变量
  }
  return flatten
}
let f = product()
console.log(f(arr2))

3. es6扩展运算符+reduce

function flatten(arr){
  return arr.reduce((acc, cur)=>{
    if(Array.isArray(cur)){
      return [...acc, ...flatten(cur)]
    }else{
      return [...acc, cur]
    }
  }, [])
}
function flatten(arr){
  return arr.reduce((acc,cur)=>{
    return acc.concat(Array.isArray(cur) ? flatten(cur) : cur)
  },[])
}

4. toString()

function flatten(arr){
  return arr.toString().split(',').map(item=> +item)
}
// 数组的toString()方法将数组转化为其字符串形式, split方法将字符串用指定分隔符切成数组，+item将字符串转化为number类型
//该方法无法处理数组成员为非数组的情况，最终会被转化为NaN

5. rest参数

function flatten(arr){
  while(arr.some(item => Array.isArray(item))){
    arr = [].concat(...arr)
  }
  return arr
}

// rest参数默认只能展开一层,扩展运算符不会修改原数组

二.数组去重的7种姿势

数组去重var arr = [1,2,2,3,4,5,6,4]

• 双重循环去重
• filter+indexOf去重
• forEach+includes去重
• reduce+sort去重
• 对象键值对去重
• Map去重
• Set去重

最优的数组去重算法是采用Map数据结构实现的算法

1. 双重循环去重

function unique(arr){
  let len = arr.length;
  for(let i=0; i<len;i++){
    for(let j=i+1; j<len;j++){
      if(arr[i]===arr[j]){
        // splice 会改变数组长度，所以要将数组长度 len 和下标 j 减一
        arr.splice(j,1)
        len--
        j--
      }
    }
  }
  return arr
}
console.log(unique(arr))

2. filter+indexOf去重

Array.prototype.unique = function(){
  return this.filter((item, index) => {
    return this.indexOf(item) === index
  })
}

3. forEach+includes去重

Array.prototype.unique = function () {
  const newArray = [];
  this.forEach(item => {
    if (!newArray.includes(item)) {
      newArray.push(item);
    }
  });
  return newArray;
}

4. reduce+sort去重

Array.prototype.unique = function(arr){
  return this.sort().reduce((init, cur) => {
    if(init.length === 0 || init[init.length-1] !== cur){
      init.push(cur)
    } 
    return init 
  }, [])
}

5. 对象键值对去重

• 利用了对象的key不可以重复的特性来进行去重
• 但需要注意：
  • 无法区分隐式类型转换成字符串后一样的值，比如 1 和 '1'
  • 无法处理复杂数据类型，比如对象（因为对象作为 key 会变成 [object Object]）
  • 特殊数据，比如 'proto'，因为对象的 proto 属性无法被重写

function Person(){
  this.a = 1
}
const p = new Person()
let arr2 = [1,'1',true,{a: 1},p, 2,3,2,4,4]
function unique(arr){
  let ret = []
  let obj = {}
  for(let item of arr){
    let tmp
    if(typeof item === 'object'){
      let constructor = Object.getPrototypeOf(item).constructor
      tmp = JSON.stringify(item) + constructor
    }else{
      tmp = typeof item + JSON.stringify(item)
    }
    if(!obj[tmp]){
      obj[tmp] = 1
      ret.push(item)
    }
  }
  return ret
}
console.log(unique(arr2), arr2)

6. filter+Map去重

function unique(arr){
  let map = new Map()
  return arr.filter(item => {
    // if(!map.has(item)){
    //   map.set(item,1)
    //   return item
    // }
    return !map.has(item) && map.set(item,1)
  })
}

7. Set去重

function unique(arr){
  let set = new Set(arr)
  return Array.from(set)
  // return [...set]
}

三.将类数组对象转为数组(4种)

• 如果一个对象的所有键名都是正整数或零，并且有length属性，那么这个对象就很像数组，语法上称为“类似数组的对象”（array-like object）
• 典型的“类似数组的对象”：
  • 函数的arguments对象，
  • 以及大多数 DOM 元素集，
  • 还有字符串

将类数组转化为真正的数组

• es6新增的扩展运算符（...）
• es6的Array.from()方法
• es6的for...of+push
• es5的slice

let divEle = document.querySelectorAll('div')
let divArr = [];
for(let item of divEle) {
    divArr.push(item)
}

let divArr = [...divEle];

let divArr2 = Array.from(divEle)

var divArr2 = Array.prototype.slice.call(divEle);

let divArr = [].concat.apply([], divEle) //concat不仅会将类数组对象转为数组，还会将数组展开

四.洗牌算法

• 它要求数组中的数打乱后，每个数出现在任意位置的概率相同

function shuffle(arr){
  for(let i=0,len=arr.length;i<len;i++){ //缓存一下数组长度
    const j =  Math.floor(Math.random()*(len-i))
    //返回一个0到len-i之间的随机整数[0,len-i-1]
    let tmp = arr[j]
    arr[j] = arr[len-i-1]
    arr[len-i-1] = tmp
  }
  return arr
}
var arr = [1, 3, 5, 7, 9]
shuffle(arr)

• 错误解法：

function shuffle(arr){
  return arr.sort(()=> Math.random()-0.5)
}
// 两数交换的概率为50%，
//这是为什么呢？问题就出在sort这个API上，对于chrome浏览器而言
//当数组长度在10以内时，sort()采用插入排序，反之，则混合使用快速排序和插入排序，
//这样会导致选取的两个交换位置的数不随机，导致数组也就没有真正打乱

五.随机数获取

• 获取一个[0,1)之间的随机数

Math.random()

• 获取一个两数之间的随机数[min, max)

Math.random()*(max-min)+min

• 获取一个两数之间的随机整数[min, max)

function getRandomInt(min, max){
  min=Math.ceil(min);
  max=Math.floor(max);
  return Math.floor(Math.random()*(max-min))+min;
}

• 获取一个两数之间的随机整数,包括两个数在内[min, max]

function getRandomInt(min, max){
  min=Math.ceil(min)
  max=Math.floor(max);
  return Math.floor(Math.random()*(max-min+1))+min;//含最大值，含最小值
}