Algorithm

题目描述

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

Example

输入: [3,2,1,5,6,4] 和 k = 2 输出: 5

题目解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

public class KthMax {

    public int findKthLargest(int[] nums, int k) {

        if (nums.length < k) return -1;

        int p = 0;
        int r = nums.length - 1;
        int q = partition(nums, p, r);

        while (k != q + 1) {
            if (k > q + 1) {
                q = partition(nums, q + 1, r);
            } else {
                q = pyrtition(nums, 0, q - 1);
            }
        }

        return nums[q];
    }

    public int partition(int[] nums, int p, int r) {

        int povit = nums[r];
        int i = p;
        for (int j = p; j < r; j++) {
            if (nums[j] > povit) {
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;
                i++;
            }
        }

        int tmp = nums[i];
        nums[i] = nums[r];
        nums[r] = tmp;
        return i;
    }

}

主要是使用快速排序算法来进行查找，先找到一个分区点q，如果k=q+1，则说明找到了，如果k>q+1则从后半区找，否则从前半区找。

Review

code-smells-too-many-problems代码味道的最后一篇，作者对整个重构前的那个长长的方法validateQuery进行了复盘。除了前面几篇提到的问题，它还有糟糕的命名，糟糕的域模型等问题。对于这种复杂代码最困难的问题就是弄清楚代码问题从哪里开始的。

重构方法

  1. 把方法分解成更小的部分
  2. 一次只处理一种问题
  3. 后退一步，试着为问题建模

作者比较喜欢第3种方法，尝试建模就是如果重新实现的话会是什么样，但是能保证重新实现的代码也是逻辑清晰吗？作者发现在实际操作中第2种方法比较好实施，确实，小小的改进能带来大的进步。毕竟那代码已经服务了成千上万的业务，直接重新建模的风险很大。

对于重构更多的建议

  1. 重命名变量/字段，提取非常小的命名好的方法
  2. 必要的地方加上注释或者评论
  3. 如果发现有些代码是为了处理边界问题，则要增加单元测试来记录这些特性
  4. 组合方法会产生更好的代码
  5. 保证重构的步伐不要太大，当遇到问题时，可以回退

评论区避免写出烂代码的建议

  1. 方法层级限制，超出后（如3层）要进行抽取
  2. 早期失败，先前重构文章中提到过
  3. 代码长度在一屏之内，一般为80或者120行

想法

这些都是在开发中会遇到的问题，如果每个人都在开始就保持着写好代码的热情，那么重构就会少很多。在修改代码时，关注修改点的同时多关注一下功能的上下文，可能会发现更好的修改点。为什么要有规范，因为这世界很乱。

Tip

推荐一个替代印象笔记的软件Joplin，软件开源，多平台支持，支持导入印象笔记内容，而且还支持命令行操作。最主要不用天天被升级高级用户而打扰。配合坚果云使用相当完美。

Share

java-api接口设计文章中讲了后端API设计的一些规则（包括请求方法，请求头，状态码等），比较有同感的是返回的错误要给错误说明，而不是错误码，因为随着业务的发展，扩展错误码会很难，而返回一个有明确说明的字符串则更有用。