问题先导
script标签中defer和async属性的区别?【
html】单行/多行文本溢出可以怎么处理？【
css】undefined和null的区别？
typeof null的结果为什么是object？【js】Vue双向绑定的原理【
vue】-
在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
知识梳理
script标签中的defer和async属性的区别？
script标签一般用于加载js脚本，我们知道js脚本是阻塞式加载和执行的，即页面解析到script标签时会暂停页面的解析，先加载脚本并执行脚本后再继续页面的解析。
而H5新增的两个属性：defer和async，可以让脚本异步加载，但脚本的执行方式有所不同，defer是延迟的意思，所以脚本会在页面加载结束再执行，而async是异步的意思，脚本只会异步加载，并立即执行。
页面的加载、脚本加载和脚本执行示意图如下所示：
总结来说就是，defer和async属性让script标签能异步加载，但async立即执行，而defer是延迟到页面加载结束再执行。
值得注意的是，当两个属性同时存在时，async的优先级更高。
关键字：html、页面脚本的加载与执行
单行和多行文本溢出如何处理？
文本溢出最常见的方式就是替换为省略号。文本溢出属性为text-overflow，有三个可选值：
- clip：默认值，裁剪溢出文本，即溢出文本会被隐藏起来
- ellipsis：省略号的意思，溢出部分替换为省略号，这也是最常用的文本溢出处理方式
- string：实验中的属性，可用指定字符特换溢出文本
除此之外，溢出文本一般还需要搭配两个属性才能正常工作，
- overflow：溢出处理，可选值有
visible、hidden、scroll和auto。一般来说，为了保证溢出文本正确被替换为省略号，需要隐藏起来才能称之为溢出文本。 -
white-space：空白处理，同样的道理，为了保证溢出文本不显示出来，需要设置为不换行，即nowrap值才行。
多行文本有时候也需要溢出显示为省略号，但这个时候whire-space对于多行来说就不起作用了，为了达到这个效果，我们需要另外使用几个属性：
text-overflow: ellpsis;
overflow: hidden;
/** 显示方式设置为box,子元素垂直排列*/
display: -webkit-box;
-webkit-box-orient: vertical;
/** 需要显示到的行数*/
-webkit-line-clamp: 3;
由于display: box、box-orient和line-clamp都是实验中的属性，一些浏览器并未支持，所以存在兼容性问题。
实例：
<div id="app" style="width: 200px;border: solid 1px #acc;display: -webkit-box;-webkit-box-orient: vertical;text-overflow: ellipsis;-webkit-line-clamp: 3;overflow: hidden;">
<p>这是一行文字，这是一行文字，这是一行文字，这是一行文字，这是一行文字，这是一行文字，</p>
<p>这是一行文字，这是一行文字，这是一行文字，这是一行文字，这是一行文字，这是一行文字，</p>
<p>这是一行文字，这是一行文字，这是一行文字，这是一行文字，这是一行文字，这是一行文字，</p>
</div>
总结来说就是，文本溢出处理需要使用text-ellipsis属性，常见的是设置为ellipsis，即省略号，但文本溢出属性需要“文本发生溢出”时才会生效，对应单行文本，通过overflow:hidden和white-space:nowarp来让单行文本达到溢出状态。
而对于多行文本，需要将父元素设置为box布局，且子元素排列方式box-orient设置为垂直排列，最后，再设置显示的行数line-clamp，这样后面为显示的行就会被替换为省略号了。
css基础、文本溢出
undefined和null的区别？typeof null的结果为什么是object？
首先从定义来说，undefined是指未初始化的变量，而null是指空对象，虽然都是基本数据类型，但本质上是不一样的数据类型。
这一点从typeof null为object也可以看出。本质上，也就是从存储方式上来说，null的存储方式和undefined也是不同的。
在第一版的js设计中，使用32位作为存储单元，并使用低三位（1-3位）表示值的类型：
000：Object类型，后续位数用于存储指向对象的引用，而null的后31位全是0，用于表示无引用，也就是空对象。
1：int类型，后续位数存储一个31位的有符号整数。
010：double类型。后续位数存储一个双精度浮点数。
100：string类型。
-
110：布尔值。
而undefined使用整数
-2^30表示，也就是说需要32位才能表示这个数字，这超出了int类型的范围。（尽管如此，我还是不太清楚这里具体是怎么区别undefined和null的，因为-2^30用32位二进制表示为11000000000000000000000000000000，同样的低三位为000，如果只按照低三位作为判断标准，那么undefined同样判断为object类型才对，没找到相关说明，难受。目前的猜测是当进行类型判断时首先判断这个数字是否与-2^30相等，相等就直接返回undefined，不相等再进一步根据低三位数值来判断数据类型，不过这种设计思路取决于开最初的设计者，无需太过关注。）
更多细节参考：《The history of “typeof null”》
关键字：js数据类型
Vue双向绑定的实现原理
Vue的双向绑定原理简单来说就是当数据发生变化时能检测到数据变化，然后做出响应。而js中的Object.defineProperty的getter和setter正是用于监听数据的读取操作的，Vue也是基于这两个api来实现数据的监听，进而实现即时响应。
双向绑定的实现有两个过程：
- 数据劫持（Observer）：也就是数据监听的定义，即使用Object.defineProperty的getter和setter来实现数据劫持（Vue3.0已使用Proxy代理对象来实现数据劫持）。
- 视图更新逻辑：当数据发生变化，就会被Observer作为观察者监听到，然后发送消息给Dep，Dep作为经纪人再将信息发送给所有订阅者，订阅者就会触发视图的更新：re-render，所以数据变化能触发视图更新。
- 双向绑定：也就是反过来视图变化也能更新数据，视图是Dom，所以视图变化我们可以通过原生Dom的事件来实现监听，然后触发数据变化，数据变化的变化又引起视图层的变化，也就实现了双向绑定效果。
关键字：Vue基础
数组中第K个最大元素
在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
题目很清晰，需要找到第K大的元素，最简单的思路就是排序，然后就能根据下标定位到第K大的数。这样做是可行的，但我们需要思考是否有优化空间。
题目要求的是查找第K大的数，实际上，如果我们不需要完全排好序就可以确认第K大位置的元素，就不需要再继续排序浪费操作次数。
不用完全排序，也就是排序是递进的过程，主要有两种排序算法：快排和堆排序。
快排，也就是快速排序算法，使用的是分而治之的思想，
- 从序列中选择一个基数
- 把数字较小的放到左边，较大的放到右边
- 对左右区间重复以上步骤，直到区间数只有一个时，排序结束
/**
* 查找序列中第K大的数字
* @param {number[]} nums
* @param {number} k
* @returns {number}
*/
function findKthLargest(nums, k) {
return quickSort(nums)[nums.length - k];
};
/**
* 快速排序
* @param {number[]} nums 待排序数组
* @param {number?} left 区间左指针
* @param {number?} right 区间右指针
* @returns {number[]}
*/
function quickSort(nums, left, right) {
if(Object.is(left, undefined)) {
left = 0;
}
if(Object.is(right, undefined)) {
right = nums.length - 1;
}
if(left >= right) {
return nums;
}
let baseIndex = left; // 基数指针
const base = nums[baseIndex];
for(let i = left;i < right + 1; i++) {
// 小于基数,放到基数左边,基数被往右“挤”一位
if(nums[i] < base) {
// 交换
nums[baseIndex] = nums[i]; // less
baseIndex++;
nums[i] = nums[baseIndex]; // more
nums[baseIndex] = base; // base
}
// 大于基数本身就在右侧，无需移动
}
quickSort(nums, left, baseIndex-1);
quickSort(nums, baseIndex+1, right);
return nums;
}
排有多种不同的位置交换方案，上面使用的是一次遍历法，从左扫到右，遇到比基数小的放到左边即可，值得注意的是，由于是往前放，需要把基数和右区间的数后移，右区间后移只需要把基数移到右区间最前端（基数后边那个数）移到右区间最后端（遍历指针的地方），基数后移一位即可。
此外，还有一种碰撞双指针法，左指针指向左区间最右侧，右指针指向右区间最左侧。所以初始时左右指针在数组区间的左右两侧。首先从左侧开始遍历，需要找较大值，找到需要移到右区间，也就是移到右指针的位置，同时，调整基数位置到左指针处。然后开始遍历右侧，找较小值，找到需要放到左区间，也就是i指针的位置，同时，调整基数的位置到右指针处。重复，直到左右指针碰撞，说明左右侧均找完。
function quickSort(nums, left, right) {
if(Object.is(left, undefined)) {
left = 0;
}
if(Object.is(right, undefined)) {
right = nums.length - 1;
}
if(left >= right) {
return nums;
}
let i = left,
j = right;
const base = nums[j];
while(i < j) {
// 寻找左侧比基数大的值
while(i < j && nums[i] <= base) {
i++;
}
nums[j] = nums[i];
nums[i] = base;
// 寻找右侧比基数小的值
while(j > i && nums[j] >= base) {
j--;
}
nums[i] = nums[j];
nums[j] = base;
}
quickSort(nums, left, j-1);
quickSort(nums, j+1, right);
return nums;
}
基于快速排序的快速选择
我们知道，快速排序是分治思想，一步一步进行排序的，其中有个数据是明确的，那就是基数的位置。每进行一次的快排，我们就可以得到基数的位置，如果要找的数在K左侧，那我们就只需要快排左区间，如果在右侧，就只需要快排右区间，直到基数就是要找的数字为止。
实际上，我们只需要把快排函数稍微修改即可：
/**
* 基于快速排序的快速查找
* @param {number[]} nums 待排序数组
* @param {number} k
* @param {number?} left 区间左指针
* @param {number?} right 区间右指针
* @returns {number}
*/
function findKthLargest(nums, k, left, right) {
if(Object.is(left, undefined)) {
left = 0;
}
if(Object.is(right, undefined)) {
right = nums.length - 1;
}
if(left >= right) {
return nums[right];
}
let i = left,
j = right;
const base = nums[j];
while(i < j) {
// 寻找左侧比基数大的值
while(i < j && nums[i] <= base) {
i++;
}
nums[j] = nums[i];
nums[i] = base;
// 寻找右侧比基数小的值
while(j > i && nums[j] >= base) {
j--;
}
nums[i] = nums[j];
nums[j] = base;
}
const d = j - (nums.length - k);
if(d == 0) {
return base;
} else if(d > 0) {
return findKthLargest(nums, k, left, j-1);
} else {
return findKthLargest(nums, k, j+1, right);
}
}
由于利用到了K值信息以及快排的特点，我们只需要对左区间或右区间进行快排就能找到答案，而无需整个数组完全排序结束。
堆排序
堆排序是利用了堆这种数据结构：
堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子的值，称为大顶堆（大根堆）。或者每个结点的值都小于或等于其左右孩子的值，称为小顶堆（小根堆）。
根据堆的特点，我们知道，大根堆能保证根元素为最大值，小根堆能保证根元素为最小值，这样，我们通过不断构建堆结构，同时不断缩小堆的规模，当堆的规模为1时，排序结束。这就是堆排序的逻辑。
- 把一个无序序列构建成一个大根堆（升序）或小根堆（降序）
- 将堆顶元素放到序列末尾
- 序列长度缩小1，重复以上步骤，直到序列长度为1，结束排序过程。
看到堆排序有点冒泡排序的韵味，都是找最大值，然后存起来，同时不断缩小查找序列的范围。然而堆排序和快排一样，时间复杂度仅为`O(nlogn)。这是因为堆这种结构带来的优化效果：当第一次构建堆之后，后续只是调整首位交换带来的变化，而无需像第一步那样重建堆。重建堆和调整堆是有很大区别的：重建是对无序序列，需要从最后一个非叶子节点开始调整，是从下往上调整，但之后的调整堆由于只有根元素发生了变化，而其他非叶子节点都已经是堆结构了，所以只需要从上往下调整，直到某个非叶子节点也变成堆结构。
堆排序实际上也可以原地排序，由于是完全二叉树，非叶子节点与左右孩子的对应关系十分明确，无需借助多余的堆结构。
/**
* 查找序列中第K大的数字
* @param {number[]} nums
* @param {number} k
* @returns {number}
*/
function findKthLargest(nums, k) {
// 1.构建大根堆
let level = nums.length;
buildHeap(nums, level);
// 2.交换首尾元素, 缩小堆级别并维护堆，重复步骤2直至堆级别为1
while(level > 1) {
// 交换首尾
level--;
const root = nums[0];
nums[0] = nums[level];
nums[level] = root;
// 重新维护堆
adjustHeap(nums, level, 0);
}
// 返回第K大的数
return nums[nums.length - k];
};
/**
* 构建大根堆
* @param {number[]} nums 序列
* @param {number} level 构建级别|范围|长度:[0 ~ level)
*/
function buildHeap(nums, level) {
// 节点(i) => (左孩子)2*i + 1, (右孩子)2*i + 2
// 最后一个非叶子节点，也就是至少存在左孩子 => 2*i + 1 <= len - 1 => i <= len/2 - 1
const lastNodeIndex = Math.ceil(level/2 - 1);
for(let i = lastNodeIndex; i >= 0; i--) {
adjustHeap(nums, level, i);
}
}
/**
* 调整大根堆
* @param {number[]} nums 序列
* @param {number} level 构建级别|范围|长度:[0 ~ level)
* @param {number} i 当前结点下标
*/
function adjustHeap(nums, level, i) {
const lastNodeIndex = Math.ceil(level/2 - 1);
if(i <= lastNodeIndex) {
let nodeVal = nums[i];
// 交换孩子结点中的最大值
const left = 2 * i + 1;
const right = 2 * i + 2;
let sweapIndex = i; // 交换结点的坐标
if(left < level && nums[left] > nodeVal) {
sweapIndex = left;
nodeVal = nums[left];
}
if(right < level && nums[right] > nodeVal) {
sweapIndex = right;
nodeVal = nums[right];
}
// 交换
if(sweapIndex != i) {
nums[sweapIndex] = nums[i];
nums[i] = nodeVal;
adjustHeap(nums, level, sweapIndex);
}
}
}
