前端面试|数组扁平化去重排序

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

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

细节知识点，均来自MDN，如下：

1. 使用Set方法去重
2. flat()数组扁平化: flat() 方法会按照一个可指定的深度递归遍历数组，并将所有元素与遍历到的子数组中的元素合并为一个新数组返回。
3. Infinity: 全局属性Infinity是一个数值，表示无穷大。
4. Array.from()：从一个类似数组或可迭代对象创建一个新的，浅拷贝的数组实例。
5. sort():对数组的元素进行排序，并返回数组。

实现：

let arr = [ [1, 2, 2], [3, 4, 5, 5], [6, 7, 8, 9, [11, 12, [12, 13, [14] ] ] ], 10];
Array.from(new Set(arr.flat(Infinity))).sort((a,b)=>{
    return a-b
})
//[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
复制代码

二、介绍下 Set、Map、WeakSet 和 WeakMap 的区别？

• Set对象允许你存储任何类型的唯一值，无论是原始值或者是对象引用;
• WeakSet 成员都是对象；成员都是弱引用，可以被垃圾回收机制回收，可以用来保存DOM节点，不容易造成内存泄漏；
• Map 本质上是键值对的集合，类似集合；可以遍历，方法很多，可以跟各种数据格式转换。
• WeakMap 只接受对象作为键名（null 除外），不接受其他类型的值作为键名；键名是弱引用，键值可以是任意的，键名所指向的对象可以被垃圾回收，此时键名是无效的；不能遍历，方法有 get、set、has、delete。

三、使用 sort() 对数组 [3, 15, 8, 29, 102, 22] 进行排序

根据 MDN 上对 Array.sort()的解释, 默认排序顺序是在将元素转换为字符串，然后比较它们的UTF-16编码顺序来进行排序。

输出：

[102, 15, 22, 29, 3, 8]
复制代码

ps: UTF-16编码顺序谁会记得。。。。。。。。。。

四、冒泡排序如何实现，时间复杂度是多少，还可以如何改进？

• 时间复杂度：一个算法执行所耗费的时间
• 空间复杂度：运行完一个程序所需内存的大小。

冒泡排序算法的原理如下：

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。

2. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。

3. 针对所有的元素重复以上的步骤，除了最后一个。

4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比比较

function sort(arr){ 
    const array = [...arr] 
    // 增加标识，如果已经排好序的数组可以直接跳出循环！！！！！
    let isOk = true 
    // 外层循环，控制趟数，每一次找到一个最大值；
    // 白话翻译：5个数，需要比较4次，所以每次比较的趟数是array.length - 1；
    for(let i = 0; i < array.length - 1; i++){ 
        // 内层循环，控制比较的次数，并且判断两个数的大小
        // 白话翻译：5个数
        // 第一次比较4次（5 - 1 - 0）
        // 第二次比较3次（5 - 1 - 1）
        // 第三次比较2次（5 - 1 - 2 ）
        // 所以每次比较的次数是 array.length - 1 - i
        for(let j = 0; j < array.length - 1 - i; j++) { 
            // 从小到大的冒泡，如果前面的数大，放到后面。
            if (array[j] > array[j + 1]) { 
                let temp = array[j] 
                array[j] = array[j + 1] 
                array[j + 1] = temp 
                isOk = false 
            } 
        }
        console.log(`第${i+1}次比较`,array)
        if(isOk){ 
            break; 
        } 
    }
    return array
}
console.log(sort([5,4, 3,2,1]))

//第1次比较 [ 4, 3, 2, 1, 5 ]
//第2次比较 [ 3, 2, 1, 4, 5 ]
//第3次比较 [ 2, 1, 3, 4, 5 ]
//第4次比较 [ 1, 2, 3, 4, 5 ]
//[ 1, 2, 3, 4, 5 ]
复制代码

需要先判断冒泡时，可以添加是不是数组，数组是否为空:

if (arr instanceof Array && arr.length > 1) {
      // 冒泡方法
}

复制代码