携程&蘑菇街&bilibili：手写数组去重、扁平化函数

Uwah commented 4 years ago

利用while循环结合some实现数组扁平，然后利用ES6 Set去重

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

while(arr.some(item => Array.isArray(item))) {

  arr = [].concat(...arr);
}

let setlist = new Set([...arr]);

console.log([...setlist]); //[123, 2, 4, 42, 1, 5, 8, 6, 54, 3, 9, 0, 7]

appbeijing commented 4 years ago

let arr = [[123,123,2,4,42,1,2,5], [5,8,6,54,3,9,9,3],0,7];
new Set([...arr.flat(Infinity)])

appbeijing commented 4 years ago

let arr = [[123,123,2,4,42,1,2,5], [5,8,6,54,3,9,9,3],0,7];
let str=JSON.stringify(arr);
let reg =/\[/g;
let reg2=/\]/g
str=str.replace(reg2,'').replace(reg,'')
new Set([...str.replace(reg2,'').replace(reg,'').split(",")])

zhuzhuoxingguang commented 4 years ago

// 扁平化  flat可以传递参数，根据要求展开depth层
const flats = arr.flat()
// 去重
[...new Set(flats)]

thxiami commented 4 years ago

// 扁平化 flat可以传递参数，根据要求展开depth层 const flats = arr.flat() // 去重 [...new Set(flats)]

题目是让自己实现数组去重和扁平化函数的, 用自带的 API 就失去意义了

thxiami commented 4 years ago

1 数组去重函数

题目中没有给出数组中元素的类型, 这里假设元素类型为number. 如果是其他类型, 对代码稍作修改即可. 这里给出两种方案, 其时间复杂度和空间复杂度不同.

方案1: 借助哈希表数据结构记录出现过的元素

遍历数组, 使用 Object 辅助记录出现过的元素

通过 Object 重建数组,也可以使用一个空数组在遍历时直接存储Object中未出现的元素.

function deduplicate(arr) {
var obj = Object.create(null)
var res = []

for (var i = 0; i < arr.length; i++) {
var element = arr[i]
if (!(element in obj)) {
  res.push(element)
}
}
return res
}

时间复杂度: O(n), n 为数组元素个数 空间复杂度: O(n)

注: 元素类型如果只有 string 或 number 中的一种类型, 使用Object 就能满足要求; 其他情况下需要借助 Map

方案 2: 借助有序数组去重的思路

  该方案可以以时间换空间, 降低空间复杂度:
    1. 先通过原地快排将数组变为有序数组, 空间复杂度 O(1), 时间复杂度 O(n*logn)
    2. 假如我们能将不重复的元素从后向前移动至数组头部, 遍历结束后在数组尾部的元素就是我们不需要的, 我们可以把它们一个个 pop 掉, 就达到了数组去重的目的

   具体操作方案: 使用快慢指针
    快指针: 遍历数组, 在前面探路
    慢指针: 为便于理解, 我们先假设当前快指针已经遍历至数组中间了, 
           并且通过某种方法将快指针遇到过的不重复的元素移动至数组头部了, 
           此时数组头部连续存放了若干个不重复的元素, 慢指针就指向这些不重复元素中的最后 1 个. 

    慢指针的作用有两个:
      1. 记录下最后一个不重复的元素, 与快指针遇到的元素进行对比.
      2. 记录下一个元素从后向前移动时应该存放的位置. 当快指针遇到不重复的元素,需要向前移动时, 直接放在慢指针的下一个索引处即可.

    解释完快慢指针的作用后, 就可以按照下面这个原则进行遍历和移动:
      1. 当快指针指向的元素与慢指针指向的元素相同时, 快指针继续前进, 慢指针不动;

      2. 当快指针指向的元素与慢指针指向的元素不同时, 慢指针前进一步, 指向了一个可以用于存储的位置, 将快指针指向的元素存至慢指针指向的位置, 然后快指针继续前进;

     举例, 比如 ary = [1,1,3,4], 快指针 i, 慢指针 j, 初始化 i=1,j=0
       1. i=1, j=0. 1 = 1, 则 j 不动, i -> 2
       2. i=2, j=0. 3 ≠ 1,  所以 j -> 1, ary[1] = ary[2], i -> 3, 此时 ary = [1,3,3,4,4]
       3. i=3, j=1. 4 ≠ 3,  所以 j -> 2, ary[2] = ary[3], i -> 4, 此时 ary = [1,3,4,4,4]
       4. i=4, j=2. 4 = 4,  所以 j 不动, i -> 3

      遍历结束, ary = [1,3,4,4], 此时 ary 的前 3 项即为所求. 取出前 3 项后者 pop 掉第 4 项即可

function dedeplicate2(arr) {
  arr.sort() // 这里使用自己写的快排代替即可

  var i = 1
  var j = 0

  while(i < arr.length) {
    if (arr[i] !== arr[j]) {
      j += 1
      arr[j] = arr[i]
    }
    i += 1
  }

  return arr.slice(0, j+1)
}

*时间复杂度: O(nlogn) 空间复杂度: O(1)**

2 扁平化函数

适用条件: 数组或类数组对象, 对于嵌套数组可通过depth指定扁平化的深度.

/**
 * @param {array}arr The array to be flatten.
 * @param {number}depth The depth level specifying how deep a nested array structure should be flattened. Defaults to 1.
 */
function flat(arr, depth = 1) {

  var res = [] 
  var unflattenDepth = depth

  var isArray = Object.prototype.toString.call(arr) === '[object Array]'
  if (isArray) {
    helper(arr)
  } else { // 将类数组对象处理为数组
    var slicedArr = Array.prototype.slice.call(arr)
    if (slicedArr.length > 0) {
      helper(slicedArr)
    }
  }

  return res

  function helper(arr) {
    unflattenDepth -= 1

    if (unflattenDepth < 0) {
      res = res.concat(arr)
    } else {
      for (var i = 0; i < arr.length; i++) {
        var element = arr[i]

        if (Object.prototype.toString.call(element) === '[object Array]') {
          helper(element)
        } else {
          res.push(element)
        }
      }
    }
  }
}

sisterAn commented 4 years ago

数组扁平化（又称数组降维）

MDN：flat() 方法会按照一个可指定的深度递归遍历数组，并将所有元素与遍历到的子数组中的元素合并为一个新数组返回

const test = ["a", ["b", "c"], ["d", ["e", ["f"]], "g"]]

// 不传参数时，默认扁平化一层
test.flat()
// ["a", "b", "c", "d", ["e", ["f"]], "g"]

// 传入一个整数参数，整数即扁平化的层数
test.flat(2)
// ["a", "b", "c", "d", "e", ["f"], "g"]

// Infinity 关键字作为参数时，无论多少层嵌套，都会转为一维数组
test.flat(Infinity)
// ["a", "b", "c", "d", "e", "f", "g"]

// 传入 <=0 的整数将返回原数组，不扁平化
test.flat(0)
test.flat(-10)
// ["a", ["b", "c"], ["d", ["e", ["f"]], "g"]]

// 如果原数组有空位，flat()方法会跳过空位。
["a", "b", "c", "d",,].flat()
// ["a", "b", "c", "d"]

Array.prototype.flat() 特性总结：

Array.prototype.flat() 用于将嵌套的数组扁平化，变成一维的数组。该方法返回一个新数组，对原数据没有影响。
不传参数时，默认扁平化一层，可以传入一个整数，表示想要扁平化的层数。
传入 <=0 的整数将返回原数组，不扁平化
Infinity 关键字作为参数时，无论多少层嵌套，都会转为一维数组
如果原数组有空位，Array.prototype.flat() 会跳过空位。

方法一：使用 reduce 方法

一次性扁平化所有：

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

// 测试
var test = ["a", ["b", "c"], ["d", ["e", ["f"]], "g"]]
flattenDeep(test)
// ["a", "b", "c", "d", "e", "f", "g"]

实现 flat 函数：

function flat(arr, depth = 1) {
    return depth > 0
        ? arr.reduce((acc, cur) => {
        if(Array.isArray(cur)) {
            return [...acc, ...flat(cur, depth-1)]
        }
        return [...acc, cur]
    } , [])
      : arr
}

// 测试
var test = ["a", ["b", "c"], ["d", ["e", ["f"]], "g"]]
// 不传参数时，默认扁平化一层
flat(test)
// ["a", "b", "c", "d", ["e", ["f"]], "g"]

// 传入一个整数参数，整数即扁平化的层数
flat(test, 2)
// ["a", "b", "c", "d", "e", ["f"], "g"]

// Infinity 关键字作为参数时，无论多少层嵌套，都会转为一维数组
flat(test, Infinity)
// ["a", "b", "c", "d", "e", "f", "g"]

// 传入 <=0 的整数将返回原数组，不扁平化
flat(test, 0)
flat(test, -10)
// ["a", ["b", "c"], ["d", ["e", ["f"]], "g"]];

// 如果原数组有空位，flat()方法会跳过空位。
var arr = ["a", "b", "c", "d",,]
flat(arr)
// ["a", "b", "c", "d"]

方法二：栈

一次性降维所有

function flattenDeep(arr) {
  const result = [] 
  // 将数组元素拷贝至栈，直接赋值会改变原数组
  const stack = [...arr]
  // 如果栈不为空，则循环遍历
  while (stack.length !== 0) {
    const val = stack.pop() 
    if (Array.isArray(val)) {
      // 如果是数组再次入栈，并且展开了一层
      stack.push(...val) 
    } else {
      // 如果不是数组，就用头插法插入到结果数组中
      result.unshift(val)
    }
  }
  return result
}

// 测试
var test = ["a", ["b", "c"], ["d", ["e", ["f"]], "g"]]
flattenDeep(animals)
// ["a", "b", "c", "d", "e", "f", "g"]

数组去重

方式一：Set（ES6）

function unique(arr) {
    return Array.from(new Set(arr))
}
// 或者
var unique = arr => [...new Set(arr)]

// 测试
var arr = [1, 2, 2, 3]
unique(arr); // [1, 2, 3]

方式二：reduce

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

// 测试
var arr = [1, 2, 2, 3]
unique(arr); // [1, 2, 3]

方法三：filter

function unique(arr) { 
    return arr.filter( (element, index, array) => {
        return array.indexOf(element) === index
    })
}

// 测试
var arr = [1, 2, 2, 3]
unique(arr); // [1, 2, 3]

linhexs commented 3 years ago

递归加Set

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

function wide(arr) {
  const result = [];
  function flatten(arr) {
    for (let i = 0; i < arr.length; i++) {
      let temp = arr[i];
      if (Array.isArray(temp)) {
        flatten(temp);
      } else {
        result.push(temp);
      }
    }
  }
  flatten(arr);
  return [...new Set(result)];
}

console.log(wide(arr));

z253573760 commented 3 years ago

const arr = [
  [123, 123, 2, 4, [42, [1, 2], 5]],
  [[5, 8], 6, [54, [3, [9, [9]]]], 3],
  0,
  7,
];
function bar(list) {
  const res = []; //结果
  const map = {}; //去重的介质
  const flat = (list) => {
    for (const item of list) {
      if (Array.isArray(item)) {
        // 如果是数组 递归
        flat(item);
      } else {
        // 不是数组
        if (!map[item]) {
          //判断是否重复
          map[item] = 1;
          res.push(item); //没重复=>添加到结果中
        }
      }
    }
  };
  flat(list);
  return res;
}

bar(arr); //[123, 2,  4, 42, 1, 5, 8, 6, 54,  3, 9, 0 ,7]
bar(arr); //[123, 2,  4, 42, 1, 5, 8, 6, 54,  3, 9, 0 ,7]

qiujie8092916 commented 3 years ago

function func(arr) {
    const set = {}

    function _(arr, ret) {
        arr.forEach(a => {
            if(Array.isArray(a)) {
                ret =_(a, ret)
            } else {
                ret = ret.concat(a)
            }
        })
        return ret
    }

    return _(arr, []).reduce((acc, v) => {
        if(set[v] === undefined) {
            acc.push(v)
            set[v] = 1
        }
        return acc
    }, [])
}

XuRan-Luo commented 3 years ago

sisterAn / JavaScript-Algorithms