ARTS 第三十六周（2019.12.02~2019.12.08）

[catcuts]

ARTS 第三十六周（2019.12.02~2019.12.08）

• Algorithm 数组中的第K个最大元素（中等难度）
• Review 使用 npm-link 辅助维护自己开发的 npm 模块
• Tip Linux 编辑计划任务的几点注意
• Share [极客专栏：数据结构与算法之美] 03 | 复杂度分析（上）：如何分析、统计算法的执行效率和资源消耗？

Algorithm 数组中的第K个最大元素（中等难度）

题目
数组中的第K个最大元素（中等难度）

代码

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function(nums, k) {
    return findByQuickSort(nums, 0, nums.length - 1, nums.length - k + 1);
};

function findByQuickSort(nums, p, r, k) {
    if (p >= r) return nums[p];
    let q = partition(nums, p, r);  // 获取分区点
    return k === q + 1 ?
        nums[q]
        : (
            k < q + 1 ?
                findByQuickSort(nums, p, q - 1, k)
                : findByQuickSort(nums, q + 1, r, k)
        );
}

function partition(nums, p, r) {
    let i = p;
    for (let j = p; j < r; j++) {
        if (nums[j] < nums[r]) {
            [nums[i], nums[j]] = [nums[j], nums[i]];
            i++;
        }
    }
    [nums[i], nums[r]] = [nums[r], nums[i]];
    return i;
}

执行结果：通过
执行用时：128 ms，在所有 javascript 提交中击败了 25.80% 的用户
内存消耗：37.6 MB，在所有 javascript 提交中击败了 7.53% 的用户

思路：
使用快速排序的思路，但似乎效果并不好。待探究。

对比：
与高分对比：
本代码运行 32 个测试用例花费约 128ms，平均一个测试用例约 4ms；
高分代码运行 32 个测试用例花费约 64ms，平均一个测试用例约 2ms。

Review 使用 npm-link 辅助维护自己开发的 npm 模块

阅读：
Understanding npm-link

点评：
如果自己开发了一个 npm 模块，发布前需要内部测试，会怎么做？

对此，我们可能会创建一个测试项目，然后把本地 npm 模块项目的代码放入测试项目 module_modules 对应子目录当中。

但这么做的缺点是，本地 npm 模块项目的每次改动，都需要把改动复制到测试项目里面，十分繁琐。

此时就可以使用 npm-link 来满足我们的需求。

只需要两步：

1. 前往本地 npm 模块项目目录，执行 npm link 将其注册为一个全局的 npm symlink；
2. 前往测试项目目录，执行 npm link 模块名称 来通过已注册的 npm symlink 使用该本地 npm 模块。

这类似于在测试项目下的 node_modules 目录中创建了一个模块名称软连接，连接到本地 npm 模块目录。

如此，所有在本地 npm 模块目录的改动，都会自动反映到测试项目下的 node_modules 对应目录当中，从而也就反应到测试项目中。

不过问题是，这和普通的软连接或者快捷方式有什么区别吗？
对此我在阅读并搜索了相关内容后仍没有答案，于是向作者提问并等待回复。
我自己的猜测是，或许这相比于手动创建软连接或快捷方式来得简便些，并且也是官方的做法。

扩展阅读：

• npm-link
• The magic behind npm link
• Use npm link for local development

Tip Linux 编辑计划任务的几点注意

Linux 中设定计划任务的命令是 crontab -e，
执行该命令后，系统会打开一个首选的编辑器，
其中可以编辑所需的计划任务。

在编辑计划任务时，有几点需要注意：

1. 不要在里面用 sudo

2. 命令要写绝对路径，如 /sbin/reboot

3. 编辑完退出后如果没有生效则可重启服务：sudo /etc/init.d/cron restart

参考：

• A Beginners Guide To Cron Jobs
• Wikipedia - cron
• How can I schedule a nightly reboot?
• A Beginners Guide To Cron Jobs
• crontab 定时任务
• Cron表达式详解
• Cron表达式生成器

Share [极客专栏：数据结构与算法之美] 03 | 复杂度分析（上）：如何分析、统计算法的执行效率和资源消耗？

分享一篇极客专栏《数据结构与算法之美》
03 | 复杂度分析（上）：如何分析、统计算法的执行效率和资源消耗？

课后思考
有人说，我们项目之前都会进行性能测试，再做代码的时间复杂度、空间复杂度分析，是否多此一举呢？
而且，每段代码都分析一下时间复杂度、空间复杂度，是不是很浪费时间呢？你怎么看待这个问题呢？
：
项目上线之前的测试，和项目提交测试之前的开发，都需要关注性能。
不同的是，前者应使用真机测试，而后者应使用复杂度分析。
开发者不能将所有的性能优化都拖到测试才来解决。