【分治难题】力扣932-漂亮数组

  |  

摘要: 一个 O(N) 分解 O(1) 合并的分治法

【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:潮汐朝夕
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


各位好,本文我们看一个非常漂亮的分治法。此前我们了解过一些分治法解决的问题,基本都是 $O(1)$ 分解,$O(N)$ 合并。本题是 $O(N)$ 分解,$O(1)$ 合并的一个例子。

要用分治法,首先要确定子问题与原问题是同一个问题,对于本题来说,要讲清楚这个事需要涉及一点仿射变换的性质。

$1 题目

对于某些固定的 N,如果数组 A 是整数 1, 2, …, N 组成的排列,使得:

对于每个 i < j,都不存在 k 满足 i < k < j 使得 A[k] * 2 = A[i] + A[j]。

那么数组 A 是漂亮数组。

给定 N,返回任意漂亮数组 A(保证存在一个)。

1
1 <= N <= 1000

示例 1:
输入:4
输出:[2,1,4,3]

示例 2:
输入:5
输出:[3,1,2,5,4]

$2 题解

算法: 分治

数学性质

如果 $A_{1}, A_{2}, …, A_{n}$ 是漂亮数组,则其仿射变换 $k \times A_{1} + b, k \times A_{2} + b, …, k \times A_{n} + b$ 也是漂亮数组。

分治法思考过程

按照正常的分治过程思考,首先将原数据 1 ~ N 分成两份:$1~N/2$ 和 $N/2+1~N$,将两部分变为漂亮数组,记为 left 和 right。

在合并阶段需要修改 left 和 right 的顺序,使得来自左半边的 i 和来自右半边的 j,都不存在 i < k < j 使得 A[k] * 2 = A[i] + A[j],并且时间复杂度不能大于 $O(N)$。

这个合并过程很难。但是如果 left 中的数字均为奇数,right 中的数字均为偶数,则合并阶段的要求自然保证,合并阶段只需要将 left 和 right 拼接起来即可,原来合并时所需的 $O(N)$ 转移到分解时了,总时间复杂度不变。此时问题难点变成了:全是奇数的左半边和全是偶数的右半边如何得到漂亮数组 left 和 right。

这时就要用到仿射变换的数学性质了:

  • 对于左半部分,它包含 1,3,… 共 $(N + 1) / 2$ 个奇数,令 k=1/2,b=1/2 可以将这 $(N+1)/2$ 个奇数映射到 $1,2,…,(N+1)/2$
  • 对于右半部分,它包含 2,4,… 共 $N / 2$ 个偶数,令 k=1/2,b=0 可以将这 $N/2$ 个偶数映射到 $1,2,…,N/2$

此时就找到了与原问题相同的子问题,只是数据规模变为了原来的一半,基于这个思路的算法流程如下:

1
2
3
4
5
6
初始问题: A[0..n-1] = 1,2,...,N

对于问题 A[l..r]:
分解:将 A[l+2i] 放进左半边,将 A[l+2i+1] 放进右半边
解决:当 r = l 时,可以直接解决,即返回 A[l]
合并:将左边的结果 left 和右边结果 right 合并

常见的分治法解决问题,通常是 $O(1)$ 分解,$O(N)$ 合并,例如归并排序,这里的算法是 $O(N)$ 分解,$O(1)$ 合并。

代码 (C++)

分解的过程的需求是将奇数位置元素置于偶数位置元素前面,相对位置不变。

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
void reOrderArray(vector<int> &A)
{
int n = A.size();
vector<int> tmp(n, -1);
for(int k = 0; k * 2 < n; ++k)
tmp[k] = A[k * 2];
for(int k = 0; k * 2 + 1 < n; ++k)
tmp[(n + 1) / 2 + k] = A[2 * k + 1];
A = tmp;
}

class Solution {
public:
vector<int> beautifulArray(int N) {
vector<int> A(N);
for(int i = 1; i <= N; ++i)
A[i - 1] = i;
solve(A, 0, N - 1);
return A;
}

private:
void solve(vector<int>& A, int l, int r)
{
if(l == r)
return;
int len = r - l + 1;

vector<int> tmp(A.begin() + l, A.begin() + r + 1);
reOrderArray(tmp);
for(int i = 0; i < len; ++i)
A[l + i] = tmp[i];

solve(A, l, l + (len - 1) / 2);
solve(A, l + (len + 1) / 2, r);
}
};

Share