实际开发过程中，会因为 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 2 其实要优于 version 1 （常数倍）