实际开发过程中，会因为 lgn 倍的时间复杂度优化而牺牲代码可读性吗

1. 场景描述：

TLDR: 在 Draft.js 富文本框架中，根据文本的 type 可以将每一行文本划分为

 'unstyled', 'header-one', 'header-two', ..., 'header-six', 'atomic', // 其他类型暂不考虑

其中，在处理 unstyled 文本时，

如果仅包含内置行内样式（BOLD, ITALIC, ...），那么直接根据 inlineStyleRanges 进行操作
如果出现了 Decorator 实现的行内样式（比如 @某人），那么必须对 inlineStyleRanges 和 EntityRanges 先进行合并操作，即根据 offset 排序数组（升序）

已知 inlineStyleRanges 和 EntityRanges 都是 sorted.

根据对象的 offset 属性，对两个 sorted 的数组进行升序排序 （ Merge Sorted Arrays)

2. 样例

类型定义：

type InlineStyleRangesType = {
    offset: number,
    length: number,
    style: 'BOLD' | 'CODE' | 'ITALIC' | 'STRIKETHROUGH' | 'UNDERLINE',
}[]

type EntityRangesType = {
    offset: number,
    length: number,
    key: number,
}[]

type SortedArrayType = {
    offset: number,
    length: number,
    key?: number,
    style?: 'BOLD' | 'CODE' | 'ITALIC' | 'STRIKETHROUGH' | 'UNDERLINE',
}[]

输入：

const a: InlineStyleRangesType = [
    { offset: 1, length: 1, style: "BOLD" },
    { offset: 9, length: 2, style: "ITALIC" },
]

const b: EntityRangesType = [
    { offset: 4, length: 1, key: 0 },
    { offset: 12, length: 1, key: 1 },
]

输出：

[
    { offset: 1, length: 1, style: "BOLD" }, 
    { offset: 4, length: 1, key: 0 },
    { offset: 9, length: 2, style: "ITALIC" },
    { offset: 12, length: 1, key: 1 },
]

3. 解法

本人解法

// version 1

function mergeSortedArrays(
    inlineStyleRanges: InlineStyleRangesType,
    entityRanges: EntityRangesType
): SortedArrayType {
    const ranges = []

    inlineStyleRanges.forEach((range) => ranges.push(range))
    entityRanges.forEach((range) => ranges.push(range))

    ranges.sort((a, b) => a.offset - b.offset)

    return ranges
}

Interview Cake 解法

// version 2

function mergeSortedArrays(
    inlineStyleRanges: InlineStyleRangesType,
    EntityRanges: EntityRangesType
): SortedArrayType {
    const ranges = (inlineStyleRanges as SortedArrayType).concat(EntityRanges)

    ranges.sort((a, b) => a.offset - b.offset)

    return ranges
}

// version 3

function mergeSortedArrays(
    inlineStyleRanges: InlineStyleRangesType,
    EntityRanges: EntityRangesType
): SortedArrayType {
    const ranges = []

    let currentIndexEntity = 0;
    let currentIndexInlineStyle = 0;
    let currentIndexMerged = 0;

    while (currentIndexMerged < (inlineStyleRanges.length + EntityRanges.length)) {

	const isInlineStyleRangesExhausted = currentIndexInlineStyle >= inlineStyleRanges.length;
	const isEntityRangesExhausted = currentIndexEntity >= EntityRanges.length;

	// Case: next comes from inlineStyleRanges
	// inlineStyleRanges must not be exhausted, and EITHER:
	// 1) EntityRanges IS exhausted, or
	// 2) The current element in inlineStyleRanges is less
	//    than the current element in EntityRanges
	if (!isInlineStyleRangesExhausted
		&& (isEntityRangesExhausted
		|| (inlineStyleRanges[currentIndexInlineStyle].offset < EntityRanges[currentIndexEntity].offset)
	)) {

		ranges[currentIndexMerged] = inlineStyleRanges[currentIndexInlineStyle];
		currentIndexInlineStyle++;

	// Case: next comes from EntityRanges
	} else {
		ranges[currentIndexMerged] = EntityRanges[currentIndexEntity];
		currentIndexEntity++;
	}

	currentIndexMerged++;
    }

    return ranges
}

4. 算法分析

	version 1	version 2	version 3
是否利用了 sorted 特性	否	否	是
时间复杂度 *	O(nlgn)	O(nlgn)	O(n)
空间复杂度	O(n)	O(n)	O(n)
代码可读性	★★★★★	★★★★	★

* version 2 其实要优于 version 1 （常数倍）