By Long Luo

This article is the solution Two Pointers Solution with Detailed Explanation of Problem 31. Next Permutation.

Intuition

• How to make a number larger?

Pick a larger number from the lower digit and swap it with the higher digit smaller number.

• How to find the permutation which is just larger than the given number?

The increase should be as small as possible.

Two Pointers

Take a example, \([3,2,1]\) which is decreasing order, there is no next permutation, it is already stable and cannot get larger.

Like \([1,5,2,4,3,2]\), how can it be just larger than the given number?

1. Scanning from right to left, find the first number which is smaller than the right digit, and swap it to the lower digit;
   • For example, \(1 5 (2) 4 3 2\), the \(2\) in the middle is the found one.
2. Scanning from right to left, searching for the first number which is larger than it, and swap them.
   • For example, \(1 5 (2) 4 (3) 2\), after swap: \(1 5 (3) 4 (2) 2\).

However, it’s not over yet!

The magnitude of the increase can be made smaller, the \(3rd\) digit from right has become slightly larger, and the last three can be made smaller.

The last three digits are definitely decreasing, and they are flipped to become \([1,5,3,2,2,4]\), which is what is required.

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.