一个文笔一般，想到哪是哪的唯心论前端小白。

前言

你今天刷力扣了吗？昨天下班时候刷了一道题，提交以后居然提示我超过了100%的人！！！

兴奋之余不得不分享一下这个快乐的过程，然而今天早上来截屏的时候已经变成了 96.35% ，快乐瞬间少了一半 ~~~

但是不得不说，力扣上大佬多入繁星呀！！！

有图有真相：

题目简介

这道题可以说是很贴切日常生产场景了，具体题目细节就不说了我描述一下生产场景吧！

现在我们老师要对 100 个学生进行一句话的评论，这个评论是英文句子(为什么是英文句子？可能是降低了难度吧)，只包含单词和空格。然后这里又两个数组，分别对应正面词汇和负面词汇，正面词汇 计 3 分，负面词汇 计 -1 分，其他词汇不计分。我们要设计一个算法把这些句子转换成得分。

转换完成以后，取出前 10 名，如果出现 得分一样的 取 id 靠前的。

题目不难吧！而且是不是很贴合实际？

原题目是这样的，我看了好几遍才看明白：

题目分析

既然粘出来了题目，那么下面就用变量来叙述了：

positive_feedback:正面词汇列表
negative_feedback:正面词汇列表
student_id: 学生id
report: 评论列表
k: 结果条数

这个场景主要是做两件事情：

1- 将评论处理一下，转换成得分，并且将得分和学生id关联起来。

转换得分的方法我想到两种：

1. 正则表达式，在每个句子前面加个0，然后使用把 空格 替换成 +，正向词汇 转换成 3，负向促词汇变成 (-1)，这样一个句子就变成了一个数学公式。
2. 使用split切割字符串，然后去和 词汇列表 比对，根据命中情况计算。
3. 暴力拆解，拿句子去和两个词汇列表比对，根据命中情况计算。

至于 得分和学生id关联起来，就更简单了，在遍历的同时记录一下就好。

2- 把结果进行排序，然后取出前 k 名。

排序这块其实我也遇到两个分歧呢：

1. 一边遍历一遍插入，跟我洋哥沟通了以后，他说这是末位淘汰制。也就是说，在一开始就留出 result(领奖台) 的接口，每次处理 report 的同时处理 result： a. 领奖台未站满人，result.length < k，直接插入并排序 b. 领奖台站满了人，新来的如果比最后一个厉害，则最后一个 out，然后新的 result 进行排序。(因为每次的result 都是排好序的，所以直接看最后一个就行) c. 领奖台站满了人，新来的如果和最后一个得分一样，则比对id。
2. 各干各的，处理评论就是处理评论，完全处理完成以后再统一排序，然后取出要的内容。

解题过程

先解释一下我的提交记录吧：

1- 解题失败是因为 ts 类型推导导致的 2- 第一次超时 在意料之中，多层循环嵌套，优化完了以后又出现了超时 3- 第二次超时 我觉得可能是我采用末位淘汰制的问题，就优化成了统一排序，但是还超时 4- 第三次超时 我就采用了现在的方式，使用Map改造两个词汇列表，然后就通过了，当时的时间是 超过了 73% 的人 5- 因为用到了 Map，那么就不需要去进行 三元运算符了，我就把 三元运算符给优化了一下，并且把两个词汇列表合成了一个，忽然就 变成了 100% ！！！ 6- 再往后就没有参考价值了，都是在研究如何更节省内存，很明显，失败啦 ~~~

贴一下代码：

function topStudents(positive_feedback: string[], negative_feedback: string[], report: string[], student_id: number[], k: number): number[] {

    // 使用 Map 改造数组
    const _map = new Map()
    positive_feedback.forEach(item => _map.set(item, 3))
    negative_feedback.forEach(item => _map.set(item, -1))

    // 处理 评论
    const result = report.map((item, i) => {
        // 切割，并处理
        const splitArr = item.split(' ').map((e:string):number => _map.get(e))
        // 求和，current: number=0，就可以直接处理 既不在正向词汇也不在负向词汇里面了
        const fen = splitArr.reduce((total:number, current:number = 0) => (total + current), 0)
        return {id: student_id[i], fen: fen}
    })

    // 排序
    result.sort((a,b) => {
        if(a.fen > b.fen) return -1
        if(a.fen < b.fen) return 1
        if(a.fen === b.fen) return a.id - b.id
    })

    // 导出 id
    return result.slice(0, k).map(item => item.id)
};

最终得出的超时的原因是因为处理 report的时候超时了，贴一下几个版本吧：

// v1.0 直接使用 includes 去遍历
const splitArr = item.split(' ').map((e:string):number => (positive_feedback.includes(e) ? 3 
    : negative_feedback.includes(e) ? -1 : 0))
const fen = splitArr.reduce((a:number, b:number) => (a + b), 0)

// v2.0 使用了两个 Map
const splitArr = item.split(' ').map((e:string):number => (positiveMap.has(e) ? 3 : negativeMap.has(e) ? -1 : 0))
const fen = splitArr.reduce((a:number, b:number) => (a + b), 0)

// v2.1 使用了一个map，并优化了命中
const splitArr = item.split(' ').map((e:string):number => _map.get(e))
const fen = splitArr.reduce((total:number, current:number = 0) => (total + current), 0)

常规方法就是我现在用的方法了，想在现有的基础上提升，我能想到的只有优化排序效率了。

其他方面的优化，我还真的没有思路，欢迎大家交流评论哈！

后记

所思即所得：

1. 数据结构的优化，会给效率带来本质上的飞跃，可以用键值对的场景，避免使用数组。
2. js 内置的 api 其实是对你知道的逻辑的一次封装，并不会 避免 遍历所带来的开销。
3. 一个开箱即用的解决方案。

写在最后的一句话，其实这个超过 100% 是有点运气的成分的，首先在这个题目比较靠后，解答的人并不多，其次typescript来解答的人就更少了，最后就是前几次连续超时处理都没有解决超时的问题，不得已才找到了真正能提高效率的方案。

就这些了！活久见！