Yangsanity's Blog

Life was like a box of chocolates

0%

发表于 分类于 阅读次数： Disqus：

有两点很明确：

  1. 负数不可能是回文数；
  2. 除了 0 以外，所有个位是 0 的数字不可能是回文数。

1

将数字本身反转，反转后的数字与原始数字进行比较，如果它们相同，那么这个数字就是回文数。

但是，要注意反转后的数字可能有溢出风险。不过上篇文章已经非常详细的介绍了溢出和反转数字应该怎么做。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public boolean isPalindrome(int x) {
    // 上述两种情况直接返回
    if (x < 0 || (x % 10 == 0 && x != 0)) {
        return false;
    }
    int copyx = x;
    // 翻转之后的数字可能超过整型的范围，用 long 来处理
    long y = 0;
    while (copyx != 0) {
        y = y * 10 + copyx % 10;
        copyx /= 10;
    }
    return x == y;
}

时间复杂度为 O(log(x))，因为 x 中大约有 lg(x) 位数字；空间复杂度为 O(1)。

2

将数字转换为字符串，通过对比字符串前后对称位置的字符是否相等来检查原始数字是否为回文。

有个可以优化的小点是我们只需遍历一半的字符串就够了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public boolean isPalindrome(int x) {
    // 上述两种情况直接返回
    if (x < 0 || (x % 10 == 0 && x != 0)) {
        return false;
    }
    String str = String.valueOf(x);
    int n = str.length();
    for (int i = 0; i < n / 2; i++) {
        // 对比字符串前后对称位置的字符是否相等
        if (str.charAt(i) != str.charAt(n - 1 - i)) {
            return false;
        }
    }
    return true;
}

时间复杂度为 O(n / 2)，忽略常数后为 O(n)；空间复杂度为 O(n)，因为我们将数字转换为了字符串。

官方题解

一个非常巧妙的办法，反转一半的数字，这必然不会导致溢出。

其中我们要解决两个问题：

  1. 如何知道反转数字的位数已经达到原始数字位数的一半？
  2. 反转后的数字 revertedNumber 如何和原始数字 x 进行比较？

可以看到：

  1. 当原始数字 x 小于或等于反转后的数字 revertedNumber 时，就意味着已经处理了一半位数的数字了；
  2. 如果是回文数，最终 revertedNumber 和 x 的关系必然如上图所示。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public boolean isPalindrome(int x) {
    // 上述两种情况直接返回
    if (x < 0 || (x % 10 == 0 && x != 0)) {
        return false;
    }
    int revertedNumber = 0;
    // 反转一半
    while (x > revertedNumber) {
        revertedNumber = revertedNumber * 10 + x % 10;
        x /= 10;
    }
    // 判断是否回文
    return x == revertedNumber || x == revertedNumber / 10;
}

时间复杂度为 O(log(x))，因为 x 中大约有 lg(x) 位数字；空间复杂度为 O(1)。

发表于 分类于 阅读次数： Disqus：

java 里数字溢出

首先得搞明白，在 Java 里数字溢出会怎样？

我们知道：Java 中 int 类型是32位有符号（即包括正值和负值）的整数。所以它是有范围的，它的范围是 [-2 ^ 31, 2 ^ 31 - 1]。

那么，如果给它的最大值加一或者给他的最小值减一会发生什么事情呢？

通过实验可以看到两点：

  1. Java 没有做数字溢出检测；
  2. 最大值和最小值的关系好像一个循环，有点类似下图，顺时针是加操作，逆时针是减操作。

如何反转一个整数

可以类比于反转字符串。我们需要不断的从 x 中“pop”出最后一位数字，然后将它“push”到 res 的后面，直到 x 为空。

怎么做呢？当然可以将 x 转成 String 然后进行操作；也可以使用辅助堆栈或数组等的帮助来进行操作。

但是好像都比较麻烦，其实我们可以直接使用数学的方法来“pop”和“push”数字。

1
2
3
4
5
6
1.pop x 的最后一个数字
  pop = x % 10;
  x /= 10;
2.将 x 的最后一个数字 push 到 res 的后面
  temp = res * 10 + pop;
  res = temp;

官方题解

其实感觉这道题可以有好多种解法，甚至可以有各种骚思路，下面来一一介绍。

先来看看官方题解的思路吧。

不知道大家有没有注意到，上面将 x 的最后一个数字 push 到 res 的后面 temp = res * 10 + pop，这个式子其实是有潜在的溢出风险的。不过我们可以很容易的事先检查这个语句是否会导致溢出：

（1）假设 res 是正数：

  1. 如果 temp = res * 10 + pop 会溢出，那么 res >= (temp - pop) / 10；
  2. 如果 res > (temp - pop) / 10，那么 temp = res * 10 + pop 必定会溢出；
  3. 如果 res = (temp - pop) / 10，那么只有当 pop > 7（其实就是 Integer.MAX_VALUE 的个位数）时，temp = res * 10 + pop 才会溢出

（2）同理可得，假设 res 是负数，只有当 pop < -8（其实就是 Integer.MIN_VALUE 的个位数）时，temp = res * 10 + pop 才会溢出。

所以事情就变得简单了，我们预先做好检查是否溢出就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * 官方题解
 */
public int reverse(int x) {
    int res = 0;
    while (x != 0) {
        int pop = x % 10;
        // 预先检查是否溢出
        if (res > Integer.MAX_VALUE / 10 || (res == Integer.MAX_VALUE / 10 && pop > Integer.MAX_VALUE % 10)) {
            return 0;
        }
        // 预先检查是否溢出
        if (res < Integer.MIN_VALUE / 10 || (res == Integer.MIN_VALUE / 10 && pop < Integer.MIN_VALUE % 10)) {
            return 0;
        }
        res = res * 10 + pop;
        x /= 10;
    }
    return res;
}

但是，再仔细深入想想：这道题给定的参数 x 本身就是合法的 int 值，而 int 的最大值和最小值开头的数字只能是 1 或 2，所以如果有最后一次循环的话，pop 的值一定是 1 或 2，因此 (res == INT_MAX / 10 && pop > 7) 和 (res == INT_MIN / 10 && pop < -8) 这两个判断肯定是不会成立的，可以省略。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * 官方题解代码优化
 */
public int reverse(int x) {
    int res = 0;
    while (x != 0) {
        int pop = x % 10;
        // 预先检查是否溢出
        if (res > Integer.MAX_VALUE / 10 || res < Integer.MIN_VALUE / 10) {
            return 0;
        }
        res = res * 10 + pop;
        x /= 10;
    }
    return res;
}

时间复杂度为 O(log(x))，因为 x 中大约有 lg(x) 位数字；空间复杂度为 O(1)。

骚操作一

将负数转为正数后再进行操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int reverse(int x) {
    // 防止 -x 溢出报错
    if (x == Integer.MIN_VALUE || x == 0) {
        return 0;
    }
    // 如果是负数，转为正数处理，并将最后结果转为负数
    if (x < 0) {
        return -reverse(-x);
    }
    int res = 0;
    while (x != 0) {
        // 判断溢出。Integer.MAX_VALUE / 10 是 214748364，假如 res 大于 214748364，那么下面 res = res * 10 + x % 10 这一行就会溢出
        if (res > Integer.MAX_VALUE / 10) {
            return 0;
        }
        res = res * 10 + x % 10;
        x /= 10;
    }
    return res;
}

骚操作二

另类判断是否溢出。

前面说了，Java 没有做数字溢出检测，那如果溢出了，溢出后的值肯定就和原值就不一样了，所以也可以通过这一点来判断是否溢出。

1
2
3
4
5
6
7
8
9
10
11
12
public int reverse(int x) {
    int ans = 0;
    while (x != 0) {
        // 判断是否溢出
        if ((ans * 10) / 10 != ans) {
            return 0;
        }
        ans = ans * 10 + x % 10;
        x /= 10;
    }
    return ans;
}

骚操作三

转为 long 处理。

int 类型范围太小导致溢出了，那么我们就找个范围更大的类型来处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
public int reverse(int x) {
    long result = 0;
    while (x != 0) {
        int pop = x % 10;
        result = result * 10 + pop;
        // 判断 int 类型是否溢出
        if (result > Integer.MAX_VALUE || result < Integer.MIN_VALUE) {
            return 0;
        }
        x /= 10;
    }
    return (int) result;
}

骚操作四

转为字符串处理，不过也用到了 long 类型。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int reverse(int x) {
    if (x == Integer.MIN_VALUE || x == 0) {
        return 0;
    }
    String strReverse = new StringBuilder(Integer.toString(Math.abs(x))).reverse().toString();
    long result = Long.parseLong(strReverse);
    // 负数转回负数
    if(x < 0) {
        result = -result;
    }
    // 判断 int 类型是否溢出
    if(result > Integer.MAX_VALUE || result < Integer.MIN_VALUE) {
        return 0;
    }
    return (int) result;
}

骚操作五

利用第三方工具类。

虽然Java 没有做数字溢出检测，但是 JDK 提供的工具类或第三方提供的工具类都可以帮我们做这个检测。

比如在 JDK 中 Math 类的 addExact() 方法，比如 apache 的 org.apache.commons.math3.util.ArithmeticUtils 类中的 addAndCheck() 方法等。所以，捕捉溢出异常也可以。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int reverse(int x) {
    int res = 0;
    while (x != 0) {
        try {
            res = Math.addExact(Math.multiplyExact(res, 10), x % 10);
            // 不能像下面这样写，因为 res * 10 已经溢出了
            // res = Math.addExact(res * 10, x % 10);
        } catch (ArithmeticException e) {
            return 0;
        }
        x /= 10;
    }
    return res;
}

凑字数

简简单单的一道题，只要动脑想，竟然可以有这么多不同的解法，是不是很神奇？

发表于 分类于 阅读次数： Disqus：

暴力

暴力查找，两层 for 循环搞定。唯一要注意的点就是题干要求数组中同一个元素不能使用两遍，所以内层循环要取外层循环之后的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * 暴力求解
 */
public int[] twoSum(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] == target) {
                return new int[]{i, j};
            }
        }
    }
    // 题干说一定有结果，所以返回 null 也没关系
    return null;
}

两层循环，时间复杂度为 O(n ^ 2)；没有用到额外空间，空间复杂度为 O(1)。

时间复杂度推导：

  1. 最好时间复杂度为 O(1)，比如 {2, 7, 11, 15}, target 为 9
  2. 最坏时间复杂度为 (n - 1) + (n - 2) + (n - 3) + … + 1 = (n - 1) * (n / 2)，省略低阶和常量，结果为 O(n ^ 2)

两遍哈希表

之前在归并排序的文章中说过，如果数据存储空间不是算法过程中的瓶颈，我们设计的算法通常优先考虑时间复杂度。

本题也可以用空间换时间的思路来进行加速。

那么我们需要一种数据结构，它既可以保存数组中每个元素与其索引的关系，又可以快速的找到某个值的索引。很显然，可以用哈希表。在 java 中我们可以直接用 HashMap。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * 遍历两遍哈希表
 */
public int[] twoSum(int[] nums, int target) {
    // 规定大小，避免扩容。K->val; V->index
    Map<Integer, Integer> map = new HashMap<>(nums.length);
    // 1.将 nums 中所有值和索引存入哈希表
    for (int i = 0; i < nums.length; i++) {
        map.put(nums[i], i);
    }
    // 2.遍历 nums，在哈希表中寻找 target - nums[i] 的值
    for (int i = 0; i < nums.length; i++) {
        int another = target - nums[i];
        // 注意还要判断一下索引不相同
        if (map.containsKey(another) && map.get(another) != i) {
            return new int[]{map.get(another), i};
        }
    }
    // 题干说一定有结果，所以返回 null 也没关系
    return null;
}

两遍循环，时间复杂度为 O(2n)，省略常数后为 O(n)；用到额外空间存储数组元素，空间复杂度为 O(n)。

一遍哈希表

时间复杂度已经为 O(n) 了，但是当 n 比较大的时候，这个常数还是会对算法造成一定的消耗。

其实，稍微换一下思路，只遍历一遍数组也能够完成。

在遍历数组时，除了将元素存入到哈希表中，还可以再回头来检查一下哈希表中是否已经存在当前元素所对应的目标元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * 遍历一遍哈希表
 */
public int[] twoSum(int[] nums, int target) {
    // 规定大小，避免扩容。K->val; V->index
    Map<Integer, Integer> map = new HashMap<>(nums.length);
    for (int i = 0; i < nums.length; i++) {
        int another = target - nums[i];
        // 如果哈希表中存在目标元素，返回
        if (map.containsKey(another)) {
            return new int[]{map.get(another), i};
        }
        // 如果哈希表中不存在目标元素，将当前元素存入哈希表
        map.put(nums[i], i);
    }
    // 题干说一定有结果，所以返回 null 也没关系
    return null;
}

一遍循环，时间复杂度为 O(n)；用到额外空间存储数组元素，空间复杂度为 O(n)。

凑字数

这道题还是比较简单的，相信很多人刚开始刷 leetcode 就是从这道题开始，这篇文章就当是回顾一下思路吧。

发表于 分类于 阅读次数： Disqus：

今天同样带来一道 leetcode 的算法题，主题同样是之前写的排序算法可不只是为了面试用的。

暴力

没啥好说的，暴力查找。我的这个写法有点类似于插入查找的思路，不同的是要从大到小进行排序，循环 k 次即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * 暴力求解
 */
public int findKthLargest(int[] nums, int k) {
    int len = nums.length, maxIndex, temp;
    for (int i = 0; i <= k; i++) {
        // [i, len] 区间中的最大值索引
        maxIndex = i;
        for (int j = i + 1; j < len; j++) {
            if (nums[j] > nums[maxIndex]) {
                maxIndex = j;
            }
        }
        // 每次找到的最大值放在左边有序区
        if (maxIndex > i) {
            // swap count and maxIndex
            temp = nums[i];
            nums[i] = nums[maxIndex];
            nums[maxIndex] = temp;
        }
    }
    return nums[k - 1];
}

平均时间复杂度为 O(k * n)，空间复杂度为 O(1)。

（我以为暴力法通不过，没想到竟然也过了）

排序

最朴素的方法，也是比较容易想到的，现成的库函数也有。（虽然也算一种方法，但直接调用库函数来排序肯定会被鄙视。。）

1
2
3
4
5
6
7
/**
 * 排序后求解
 */
public int findKthLargest(int[] nums, int k) {
    Arrays.sort(nums);
    return nums[nums.length - k];
}

时间复杂度为 O(nlogn)，空间复杂度为 O(1)，原地排序。

堆

堆的性质及两个类型大家肯定还记得，解本题用一个小顶堆即可。

我们要保证堆中只有 k 个元素，当堆中元素超过 k 个时，就让最小元素（堆顶元素）出队。这样当所有元素经过这个操作后，堆中剩下的元素是待查找数组中的 k 个最大元素，而堆顶元素是这 k 个元素中的最小值，也就是答案。

java 中刚好也提供了现成的类可以用，那就是 PriorityQueue，而且它默认就是小顶堆，可真是省了不少事。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * 利用小顶堆性质求解
 */
public int findKthLargest(int[] nums, int k) {
    // 小顶堆，k + 1 防止没必要的扩容（看过源码就会知道）
    PriorityQueue<Integer> heap = new PriorityQueue<>(k + 1);
    for (int n: nums) {
        heap.add(n);
        // 保证小顶堆中只有 k 个元素
        if (heap.size() > k) {
            heap.poll();
        }
    }
    // 直接返回堆顶元素
    return heap.poll();
}

时间复杂度为 O(nlogk)，空间复杂度为 O(k)，用于存储堆元素。

利用快排思路

传送门：快速排序

之前的文章详细介绍过快排，那么我们知道两点：

  1. 数组中的第 k 个最大元素也就是第 n - k 个最小元素；
  2. 快排的 partition 操作，每次返回基准值在数组中排好序后的正确位置。

快排在每次 partition 结束后，还会再对基准值左右两边的子数组进行 partition 操作。而对于这道题，根据上边的第一点，我们可以在每次 partition 结束后，判断出正确结果在基准值左边还是右边，直接对某一边的子数组进行 partition 即可，直到找到正确结果。

这个算法和快排都是 Tony Hoare 发明的，因此也被称为 Hoare 选择算法。

之前详细介绍过快排，这里直接用三路快排来实现。

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
/**
 * 利用快排思路求解
 */
public int findKthLargest(int[] nums, int k) {
    return findKthLargestHelper(nums, 0, nums.length - 1, nums.length - k);
}

private int findKthLargestHelper(int[] nums, int left, int right, int k) {
    int randomIndex = (int) (Math.random() * (right - left + 1)) + left;
    int temp = nums[left];
    nums[left] = nums[randomIndex];
    nums[randomIndex] = temp;
    int pivot = nums[left], lt = left, gt = right + 1, i = left + 1;
    while (i < gt) {
        if (nums[i] < pivot) {
            temp = nums[i];
            nums[i] = nums[lt + 1];
            nums[lt + 1] = temp;
            i ++;
            lt ++;
        } else if (nums[i] > pivot) {
            temp = nums[i];
            nums[i] = nums[gt - 1];
            nums[gt - 1] = temp;
            gt --;
        } else {
            i ++;
        }
    }
    nums[left] = nums[lt];
    nums[lt] = pivot;
    if (k < lt) {
        return findKthLargestHelper(nums, left, lt - 1, k);
    } else if (k > gt - 1) {
        return findKthLargestHelper(nums, gt, right, k);
    } else {
        return pivot;
    }
}

平均时间复杂度为 O(n)，空间复杂度为 O(1)，原地查找。不得不说，这个时间复杂度还是比较令人满意的。

发表于 分类于 阅读次数： Disqus：

树状数组，又称二元索引树（Binary Indexed Tree），又以其发明者命名为 Fenwick 树。最早由 Peter M. Fenwick 于 1994 年提出。

上篇文章最后已经把树状数组能干什么说的非常清楚了。再简单回顾下，树状数组是一种可以动态维护数组前缀和的数据结构，它的主要功能是：

  1. 单点更新 update(i, v)：把序列 i 位置的数加上一个值 v；
  2. 区间查询 query(i)：查询序列 [1⋯i] 区间的区间和，即 i 位置的前缀和

其中单点更新和区间查询的时间复杂度都是 O(logn)，n 为需要维护前缀和的数组的长度。

重点是，单点更新和区间查询的时间复杂度都是 O(logn) 它是怎么做到的？

树状数组的神秘面纱

先来看看它到底长什么样子。（我感觉长的跟跳表还有点像）

树状数组

其中，数组 A 是原数组，数组 C 就是树状数组（现在终于知道它为什么叫树状数组了吧，长的就像树）。

从图中可以看到数组 A 和数组 C 之间的关系：

C1 = A1
C2 = A1 + A2
C3 = A3
C4 = A1 + A2 + A3 + A4
C5 = A5
C6 = A5 + A6
C7 = A7
C8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8
… …

这里有个有趣的性质：设数组 C 的节点编号为 n，则 C[n] 管辖的区间为数组 A 从 n 往左连续 2 ^ k（k 为 n 二进制末尾 0 的个数）个元素。因为这个区间最后一个元素必然为 A[n]，所以 C[n] = Sum[ A[n – 2 ^ k + 1], A[n] ]。

好像有点绕，用 C[10] 来举个例子。10 的二进制表示为 1010，则 2 ^ k（k 为 10 二进制末尾 0 的个数，所以 k = 1）为 2 ^ 1 = 2，则 C[10] 管辖的区间为数组 A 从 10 往左连续 2 个元素，即 C[10] = Sum[ A[10 – 2 ^ 1 + 1], A[10] ] = A[9] + A[10]。

看到这里，大家应该就有感觉了，为什么树状数组能做到单点更新和区间查询的时间复杂度都是 O(logn) ？正是因为它把线性结构转化成了树状结构，从而进行跳跃式的扫描！

到这里，就得先说一个重要的函数 lowbit，它就是用来计算上面说的 2 ^ k 的快捷方法。

lowbit

lowbit(k) 的结果是：只保留 k 的二进制中最低位的 1。举个例子，lowbit(10)，10 的二进制是 1010，则 lowbit(10) = 0010（只保留 1010 中最低位的 1）。

而 lowbit 有两种实现方式，都要用到位运算。

实现方式一

我们知道，在计算机中，负数的二进制以原码的补码形式来表示，负数的补码为对该数的原码除符号位外各位取反，然后在最后一位加 1。

比如 -10 用二进制来表示：-10 的原码为 1000 0000 0000 0000 0000 0000 0000 1010；反码为 1111 1111 1111 1111 1111 1111 1111 0101；补码为 1111 1111 1111 1111 1111 1111 1111 0110。

此时，10 & -10 是什么情况呢？

0000 0000 0000 0000 0000 0000 0000 1010 & 1111 1111 1111 1111 1111 1111 1111 0110 = 0000 0000 0000 0000 0000 0000 0000 0010。惊喜的发现，其实结果就是 lowbit(10)。

（附 & 运算规则：0 & 0 = 0；0 & 1 = 0；1 & 0 = 0；1 & 1 = 1）

1
2
3
public int lowbit(int k) {
  return k & (-k);
}

实现方式二

我们知道，将一个二进制数减一，得到的结果是：从最低位的 1 开始后面的部分都与之前相反。

比如 10 的二进制表示为 1010，那么 9 的二进制表示为 1001。

此时，10 ^ 9 是什么情况呢？很简单，1010 ^ 1001 = 0011。

此时，10 & (10 ^ 9) 又是什么情况呢？也很简单，1010 & 0011 = 0010。我们又惊喜的发现，其实结果就是 lowbit(10)。

（附 ^ 运算规则：0 ^ 0 = 0；0 ^ 1 = 1；1 ^ 0 = 1；1 ^ 1 = 0）

1
2
3
public int lowbit(int k) {
  return k & (k ^ (k - 1));
}

树状数组实现思路

有了 lowbit 函数，我们就可以把上图中的 A 数组和 C 数组联系起来了！

单点更新

在修改时也要对该节点的所有父节点进行修改。比如在上图中要修改 C[1]，那么 C[2]，C[4]，C[8]，C[16] 也要做修改。

那不看图的话怎么知道该节点的所有父节点呢？不难，1 + lowbit(1) = 2，2 + lowbit(2) = 4，4 + lowbit(4) = 8，8 + lowbit(8) = 16，（16 + lowbit(16) = 32 超出了数组大小自然不用考虑）。

区间查询

比如求上图中 [1, 14] 的区间和，从图中可以看到：
Sum[1, 14] = C[14] + C[12] + C[8] = Sum[ A[13], A[14] ] + Sum[ A[9], A[12] ] + Sum[ A[1], A[8] ] = Sum[ A[1], A[14] ]。

那不看图的话怎么算出 12 和 8 呢？也不难，14 - lowbit(14) = 12，12 - lowbit(12) = 8，（8 - lowbit(8) = 0 自然不用考虑）。

树状数组求和图示（图片来源网络，侵删）

树状数组代码

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
/**
 * 树状数组
 */
public class FenwickTree {

    /**
     * 上图中的 C 数组
     */
    private int[] tree;

    private int len;

    public FenwickTree(int len) {
        this.tree = new int[len + 1];
        this.len = len;
    }

    /**
     * 单点更新：把数组 i 位置的值加上 v
     */
    public void update(int i, int v) {
        // 类比上图，从下到上进行更新
        while (i <= this.len) {
            this.tree[i] += v;
            i += lowbit(i);
        }
    }

    /**
     * 区间查询：查询序列 [1 ⋯ i] 区间的区间和，即 i 位置的前缀和
     */
    public int query(int i) {
        // 类比上图，从右到左查询
        int sum = 0;
        while (i > 0) {
            sum += this.tree[i];
            i -= lowbit(i);
        }
        return sum;
    }

    private int lowbit(int x) {
        return x & (-x);
    }
}

求数组中的逆序对

具体思路上篇文章最后已经介绍了，不再赘述，直接来看代码吧。

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
/**
 * 用离散化树状数组求求数组中的逆序对
 * 离散化原因：使得数字更紧凑，节约树状数组的空间
 */
public int reversePairs(int[] nums) {
    int len = nums.length;
    if (len < 2) {
        return 0;
    }
    // 去重并排序
    Set<Integer> treeSet = new TreeSet<>();
    for (int num : nums) {
        treeSet.add(num);
    }
    // 把排名存在 HashMap 里方便查询
    Map<Integer, Integer> rankMap = new HashMap<>();
    int rankIndex = 1;
    for (Integer num : treeSet) {
        rankMap.put(num, rankIndex++);
    }
    // 在树状数组内部完成前缀和的计算
    // 规则是：从后向前，先给对应的排名 + 1，再查询前缀和
    FenwickTree fenwickTree = new FenwickTree(rankMap.size());
    int count = 0;
    for (int i = len - 1; i >= 0; i--) {
        int rank = rankMap.get(nums[i]);
        fenwickTree.update(rank, 1);
        count += fenwickTree.query(rank - 1);
    }
    return count;
}

提交，完美通过！

凑字数

借用一句话来总结树状数组：树状数组巧妙地利用了二分，它并不神秘，关键是巧妙！