# 第二十八周ARTS总结

# Algorithm

Find First and Last Position of Element in Sorted Array (opens new window)

0ms | 100.00% Run time
43.4MB | 97.16% Memory

public int[] searchRange(int[] nums, int target) {
    int[] ans = new int[]{-1, -1};

    // 处理空数组的情况
    if (nums == null || nums.length == 0) {
        return ans;
    }

    // 处理长度为1的情况
    if (nums.length == 1) {
        if (nums[0] == target) {
            ans[0] = 0;
            ans[1] = 0;
        }

        return ans;
    }

    int left = 0;
    int right = nums.length - 1;

    int l1 = -1, r1 = -1, l2 = -1, r2 = -1;

    // 找到target所在的范围(时间复杂度：logn)
    while (true) {

        // 如果范围内只有两个数，则结果已出
        if (right - left == 1) {
            if (nums[left] == target && nums[right] == target) {
                ans[0] = left;
                ans[1] = right;
            } else if (nums[left] != target && nums[right] == target) {
                ans[0] = right;
                ans[1] = right;
            } else if (nums[left] == target && nums[right] != target) {
                ans[0] = left;
                ans[1] = left;
            }

            return ans;
        }

        int middle = (left + right) / 2;

        // 切掉一半
        if (nums[middle] > target) {
            right = middle;
            continue;
        }

        // 切掉一半
        if (nums[middle] < target) {
            left = middle;
            continue;
        }

        // 此时`nums[middle] == target`
        l1 = left;
        r1 = middle;
        l2 = middle;
        r2 = right;
        break;
    }

    // 此时证明nums中有target值
    if (l1 != -1) {
        // 找从左往右的第一个target值(时间复杂度logn)
        while (true) {
            if (r1 - l1 == 1) {
                if (nums[l1] == target) {
                    ans[0] = l1;
                } else if (nums[r1] == target) {
                    ans[0] = r1;
                }
                break;
            }

            int m1 = (l1 + r1) / 2;
            if (nums[m1] == target) {
                r1 = m1;
            } else {
                l1 = m1;
            }
        }

        // 找从右往左的第一个target值(时间复杂度logn)
        while (true) {
            if (r2 - l2 == 1) {
                if (nums[r2] == target) {
                    ans[1] = r2;
                } else if (nums[l2] == target) {
                    ans[1] = l2;
                }
                break;
            }

            int m2 = (l2 + r2) / 2;
            if (nums[m2] == target) {
                l2 = m2;
            } else {
                r2 = m2;
            }
        }
    }

    return ans;
}

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107

# Review

# Tip

Java的一些规范
- MyBatis不要为了多个查询条件而写1 = 1
  当遇到多个查询条件，使用where 1=1可以很方便的解决我们的问题，但是这样很可能会造成非常大的性能损失，因为添加了where 1=1的过滤条件之后，数据库系统就无法使用索引等查询优化策略，数据库系统将会被迫对每行数据进行扫描（即全表扫描）以比较此行是否满足过滤条件，当表中的数据量较大时查询速度会非常慢；此外，还会存在SQL注入的风险。
- 迭代entrySet()获取Map的key和value
  当循环中只需要获取Map的主键key时，迭代keySet()是正确的；但是，当需要主键key和取值value时，迭代entrySet()才是更高效的做法，其比先迭代keySet()后再去通过get取值性能更佳。
- 使用Collection.isEmpty()检测空
  使用Collection.size()来检测是否为空在逻辑上没有问题，但是使用Collection.isEmpty()使得代码更易读，并且可以获得更好的性能；除此之外，任何Collection.isEmpty()实现的时间复杂度都是O(1)，不需要多次循环遍历，但是某些通过Collection.size()方法实现的时间复杂度可能是O(n)。
- 初始化集合时尽量指定其大小
  尽量在初始化时指定集合的大小，能有效减少集合的扩容次数，因为集合每次扩容的时间复杂度很可能时O(n)，耗费时间和性能。
- 使用StringBuilder拼接字符串
  一般的字符串拼接在编译期Java会对其进行优化，但是在循环中字符串的拼接Java编译期无法执行优化，所以需要使用StringBuilder进行替换。
- 若需频繁调用Collection.contains方法则使用Set
  在Java集合类库中，List的contains方法普遍时间复杂度为O(n)，若代码中需要频繁调用contains方法查找数据则先将集合list转换成HashSet实现，将O(n)的时间复杂度将为O(1)。
- 使用静态代码块实现赋值静态成员变量
  对于集合类型的静态成员变量，应该使用静态代码块赋值，而不是使用集合实现来赋值。
- 删除未使用的局部变量、方法参数、私有方法、字段和多余的括号
- 工具类中屏蔽构造函数
  工具类是一堆静态字段和函数的集合，其不应该被实例化；但是Java为每个没有明确定义构造函数的类添加了一个隐式公有构造函数，为了避免不必要的实例化，应该显式定义私有构造函数来屏蔽这个隐式公有构造函数。
- 删除多余的异常捕获并跑出
  用catch语句捕获异常后，若什么也不进行处理，就只是让异常重新抛出，这跟不捕获异常的效果一样，可以删除这块代码或添加别的处理。
- 字符串转化使用String.valueOf(value)代替"" + value
  把其它对象或类型转化为字符串时，使用String.valueOf(value)比""+value的效率更高。
- 避免使用BigDecimal(double)
  BigDecimal(double)存在精度损失风险，在精确计算或值比较的场景中可能会导致业务逻辑异常。
- 返回空数组和集合而非null
  若程序运行返回null，需要调用方强制检测null，否则就会抛出空指针异常；返回空数组或空集合，有效地避免了调用方因为未检测null而抛出空指针异常的情况，还可以删除调用方检测null的语句使代码更简洁。
- 优先使用常量或确定值调用equals方法
  对象的equals方法容易抛空指针异常，应使用常量或确定有值的对象来调用equals方法。
- 枚举的属性字段必须是私有且不可变
  枚举通常被当做常量使用，如果枚举中存在公共属性字段或设置字段方法，那么这些枚举常量的属性很容易被修改；理想情况下，枚举中的属性字段是私有的，并在私有构造函数中赋值，没有对应的Setter方法，最好加上final修饰符。
- String.split(String regex)部分关键字需要转译
  使用字符串String的split方法时，传入的分隔字符串是正则表达式，则部分关键字（比如.[]()|等）需要转义。

暂无内容

← 第二十七周ARTS总结第二十九周ARTS总结 →

# 第二十八周ARTS总结

# Algorithm

# Review

# Tip

# Share