Long Luo's Life Notes

By Long Luo

之前的文章 傅里叶变换(Fourier Transform) 详细介绍了傅里叶变换 \((\textit{Fourier Transform})\) 是什么和做什么，相信你已经感受到了傅里叶变换的强大之处。

但理论要联系实际，今天我们就来学习 快速傅里叶变换 \((\textit{Fast Fourier Transform, FFT})\) ¹ 的实际运用：多项式乘法。

快速傅里叶变换(Fast Fourier Transform, FFT)

快速傅里叶变换 \((\textit{Fast Fourier Transform, FFT})\) ² 是一种可在 \(O(nlogn)\) 时间内完成的 离散傅里叶变换³ \((\textit{Discrete Fourier transform, DFT})\) 算法。

FFT可以做什么？

傅里叶变换 \((\textit{Fourier Transform})\) 本质上是信号与三角函数进行卷积运算，而快速傅里叶变换 \((\textit{FFT})\) 就是提高卷积的计算效率，时间复杂度从 \(O(n^2)\) 降低到 \(O(n \log n)\)。

\(\textit{FFT}\) 在算法中的运用主要是用来加速多项式乘法或大数乘法。

多项式乘法

正如之前的文章 卷积(Convolution) 所说，多项式乘法也是一种卷积运算。

在计算中，泰勒级数⁴ 可以使用多项式函数来逼近一个函数，所以计算中多项式乘法非常重要。

大数乘法

超大数字乘法，可以参考 超大数字的四则运算是如何实现的呢？ 。朴素的算法就是列竖式做乘法，算法时间复杂度为 \(O(n^2)\) ，如果数字太大的话，效率也不够高，如果应用 \((\textit{FFT})\) 则可以使算法时间复杂度降至 \(O(n \log n)\)。

不妨设十进制数字 \(num = 123456789\) ，很容易知道：

\[ 123456789 = 1 \times 10^8 + 2 \times 10^7 + 3 \times 10^6 + 4 \times 10^5 + 5 \times 10^4 + 6 \times 10^3 + 7 \times 10^2 + 8 \times 10^1 + 9 \times 10^0 \]

令 \(x = 10\)，则可以转化为：

\[ 1 \times x^8 + 2 \times x^7 + 3 \times x^6 + 4 \times x^5 + 5 \times x^4 + 6 \times x^3 + 7 \times x^2 + 8 \times x^1 + 9 \times x^0 \]

所以大数乘法就是 \(x = 10\) 情况下的多项式乘法！

那下面我们就以多项式乘法的为例来学习快速傅里叶变换 \((\textit{FFT})\) 具体是如何做的。

多项式

在学习多项式乘法之前，我们需要先学习下有关多项式的知识。

多项式有两种表示方法: 系数表示法与点值表示法。

系数表示法

设多项式 \(A(x)\) 为一个 \(n\) 项 \(n - 1\) 次的多项式，显然，所有项的系数组成的系数向量 \((a_0, a_1, a_2, \dots, a_{n-1})\) 唯一确定了这个多项式。

\[ A(x) = \sum_{i=0}^{n-1}a_i \cdot x^i = a_0 + a_1x^1 + a_2x^2 + \cdots + a_{n-1}x^{n-1} \iff A(x) = {a_0, a_1, \dots, a_{n-1}} \]

点值表示法

点值表示法是把这个多项式看成一个函数，从其中选取 \(n\) 个不同的点，从而利用这 \(n\) 个点来唯一地表示这个函数。

设

\[ \begin{array}{c} A(x_0) = y_0 = a_0 + a_1x_0+a_2x_0^2+a_3x_0^3+ \cdots + a_{n-1}x_0^{n-1} \\ A(x_1) = y_1 = a_0 + a_1x_1+a_2x_1^2+a_3x_1^3+ \cdots + a_{n-1}x_1^{n-1} \\ A(x_2) = y_2 = a_0 + a_1x_2+a_2x_2^2+a_3x_2^3+ \cdots + a_{n-1}x_2^{n-1} \\ \vdots \\ A(x_{n-1}) = y_{n-1} = a_0 + a_1x_{n-1}+a_2x_{n-1}^2+a_3x_{n-1}^3+ \cdots + a_{n-1}x_{n-1}^{n-1} \end{array} \]

那么用点值表示法表示 \(A(x)\) 如下：

\[ A(x) = a_0 + a_1x + a_2x^2 + \cdots + a_{n-1}x^{n-1} \iff A(x) = {(x_0,y_0), (x_1,y_1), \cdots,(x_{n-1},y_{n-1})} \]

为什么用 \(n\) 个不同点就能唯一地表示一个 \(n-1\) 次函数？

证明如下：

• Proof \(1\) :

两点确定一条直线。再来一个点，能确定这个直线中的另一个参数，那么也就是说 \(n\) 个点能确定 \(n-1\) 个参数（不考虑倍数点之类的没用点）。

• Proof \(2\)⁵ :

假设原命题不成立，则存在两个不同的 \(n-1\) 次多项式函数 \(A(x)\) ，\(B(x)\) ，那么 \(A(x)\) ，\(B(x)\) 有 \(n-1\) 个交点，即任何 \(i \in [0, n-1]\)，有 \(A(x_i) = B(x_i)\) 。

令 \(C(x) = A(x) - B(x)\) ，则 \(C(x)\) 也是一个 \(n-1\) 次多项式。对于任何 \(i \in [0, n-1]\)，都有 \(C(x_i) = 0\) 。

即 \(C(x)\) 有 \(n\) 个根，这与代数基本定理（一个 \(n-1\) 次多项式在复数域上有且仅有 \(n-1\) 个根）相矛盾，故 \(C(x)\) 并不是一个 \(n-1\) 次多项式，推导矛盾。

故原命题成立。

By Long Luo

This article is the solution 2 Approaches: Two Pointers and Recursion of Problem 344. Reverse String .

Here shows 2 Approaches to slove this problem, Recursion and Two Pointers.

Two Pointers

Most of us may think about two pointers solution.

We need \(\dfrac {N}{2}\) times swap.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

public void reverseString(char[] s) {
    if (s == null || s.length <= 1) {
        return;
    }
    
    int left = 0;
    int right = s.length - 1;
    while (left < right) {
        char ch = s[left];
        s[left] = s[right];
        s[right] = ch;
        left++;
        right--;
    }
}

or use For Loop:

1
2
3
4
5
6
7
8
9
10
11
12
13

// Two Pointers Opt O(n) O(1)
public static void reverseString_tp_opt(char[] s) {
    if (s == null || s.length <= 1) {
        return;
    }

    int n = s.length;
    for (int left = 0, right = n - 1; left < right; ++left, --right) {
        char tmp = s[left];
        s[left] = s[right];
        s[right] = tmp;
    }
}

Analysis

• Time Complexity: \(O(n)\)
• Space Complexity: \(O(1)\)

By Long Luo

这篇文章是 Leetcode 1385. 两个数组间的距离值 的 力扣社区题解 。

方法一：模拟

对于 \(arr1\) 数组中的每一个元素 \(x\)，枚举数组 \(arr2\) 中的每一个元素 \(y\)，检查是否对于每一个 \(y\) 都有 \(|x - y| > d\)，如果是，就将答案增加 \(1\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

// BF time: O(m * n) space: O(1)
public static int findTheDistanceValue_bf(int[] arr1, int[] arr2, int d) {
	int ans = 0;
	for (int x : arr1) {
		boolean flag = true;
		for (int y : arr2) {
			if (Math.abs(x - y) <= d) {
				flag = false;
			}
		}

		ans += flag ? 1 : 0;
	}

	return ans;
}

复杂度分析

• 时间复杂度：\(O(mn)\)，其中 \(arr1\) 中元素个数为 \(m\)，\(arr2\) 中元素个数为 \(n\)。
• 空间复杂度：\(O(1)\)。

方法二： 二分搜索

在方法一中，要知道是否每一个 \(y\) 是不是满足 \(|x - y| > d\)，我们枚举了所有 \(y\)。

实际上因为 \(d >= 0\)，假如arr2存在某个 \(y\) 满足 \(x - d \le y \le x + d\)，那么arr1中的数 \(x\) 就不满足要求。

先对arr2进行排序，之后枚举arr1每个元素 \(x\)，利用二分搜索来判断 \(x\) 是否满足要求。

By Long Luo

This article is the solution 6 Approaches: Brute Force, Row Search, Column Search, One Binary Search, 2D Coordinate Axis of Problem 74. Search a 2D Matrix.

Here are 6 approaches to solve this problem: Brute Force, Binary Search(Row), Binary Search(Column), One Binary Search and \(2D\) Coordinate Axis.

BF(2 Loops)

It’s easy to use \(2\) Loops to traverse the entire matrix to find the target.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

// BF
public static boolean searchMatrix_bf(int[][] matrix, int target) {
    int row = matrix.length;
    int col = matrix[0].length;

    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            if (matrix[i][j] == target) {
                return true;
            }
        }
    }

    return false;
}

Notice that the first integer of each row is greater than the last integer of the previous row.

We can optimize the code before.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

// BF Opt
public static boolean searchMatrix_bf_opt(int[][] matrix, int target) {
    int row = matrix.length;
    int col = matrix[0].length;

    if (matrix[0][0] > target || matrix[row - 1][col - 1] < target) {
        return false;
    }

    for (int i = 0; i < row; i++) {
        if (target >= matrix[i][0] && target <= matrix[i][col - 1]) {
            for (int j = 0; j < col; j++) {
                if (matrix[i][j] == target) {
                    return true;
                }
            }
        }
    }

    return false;
}

Analysis

• Time Complexity: \(O(m \times n)\)
• Space Complexity: \(O(1)\)

Find Row First, then Column Binary Search

We can scanning the rows of the matrix, If the \(\textit{target}\) is larger than the last element of this row, the target must not be in this row, but only in the lower row of the matrix.

If we find the row which the target may appears, search this row.

By Long Luo

这篇文章是 287. 寻找重复数 的题解。

目前这道题，经过自己摸索和参考 官方题解: 寻找重复数 ，目前发现了9种方法。

这些方法可以分为以下几类：

• 需要额外空间，需要修改原始数组 \(O(\log n)\) space
  • 排序 - \(O(n \log n)\) time
• 需要额外空间，不修改原始数组 \(O(n)\) space
  • 计数法 - \(O(n)\) time
  • Set - \(O(n)\) time
• 不需要额外空间，需要修改原始数组 \(O(1)\) space
  • 标记法 - \(O(n)\) time
  • 索引排序 - \(O(n)\) time
• 不需要额外空间，不修改原始数组 \(O(1)\) space
  • 暴力 - \(O(n^2)\) time
  • 二分搜索 - \(O(n \log n)\) time
  • 位运算 - O(n n) time
  • 双指针 - \(O(n)\) time

因为题目要求：

1. 必须不修改数组 \(\textit{nums}\)；
2. 只用常量级 \(O(1)\) 的额外空间。

因此我们先从需要修改数组的方案开始，下面我们就来一一分析：

需要额外空间，需要修改原始数组

方法一：排序

先对数组进行排序，然后遍历数组，如果出现重复数字既是答案。

1
2
3
4
5
6
7
8
9
10
11
12

// Sort
public static int findDuplicate_sort(int[] nums) {
    Arrays.sort(nums);
    int len = nums.length;
    for (int i = 1; i < len; i++) {
        if (nums[i] == nums[i - 1]) {
            return nums[i];
        }
    }

    return len;
}

复杂度分析

• 时间复杂度：\(O(n \log n + n)\)，其中 \(n\) 为 \(\textit{nums}\) 数组的长度，\(O(\log n)\) 排序复杂度，总时间复杂度为 \(O(n \log n + n)\)。
• 空间复杂度：\(O(\log n)\)，排序需要使用 \(O(\log n)\) 空间。

需要额外空间，不修改原始数组

方法二：计数法

因为数组元素值的范围是 \([1, n]\) 之间，那么可以使用一个数组来记录数字出现次数，次数大于 \(1\) 即为答案。

1
2
3
4
5
6
7
8
9
10
11
12
13

// Count
public static int findDuplicate_count(int[] nums) {
    int len = nums.length;
    int[] cnt = new int[len + 1];
    for (int i = 0; i < len; i++) {
        cnt[nums[i]]++;
        if (cnt[nums[i]] > 1) {
            return nums[i];
        }
    }

    return len;
}

复杂度分析

• 时间复杂度：\(O(n)\)，其中 \(n\) 为 \(\textit{nums}\) 数组的长度。
• 空间复杂度：\(O(n)\)，需要新建一个长度为 \(n\) 的数组。

方法三：HashSet

同方法二，这里使用HashSet来记录数组元素。

1
2
3
4
5
6
7
8
9
10
11
12

// Set
public static int findDuplicate_set(int[] nums) {
    Set<Integer> set = new HashSet<>();
    int len = nums.length;
    for (int i = 0; i < len; i++) {
        if (!set.add(nums[i])) {
            return nums[i];
        }
    }

    return len;
}

复杂度分析

• 时间复杂度：\(O(n)\)，其中 \(n\) 为 \(\textit{nums}\) 数组的长度。
• 空间复杂度：\(O(n)\)。