LeetCode 932: beautiful array

发表于 | | 阅读次数:
字数统计: 361 | 阅读时长 ≈ 1

题目链接

https://leetcode.com/problems/beautiful-array/

题意

给定一个数字N <= 1000, 构造一个 1 - N 的排列并保证:

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

题目类型

构造

题目分析

构造答案时可以把奇数全部放在左边偶数全部放在右边，奇数和偶数相加为奇数，这样就只可能奇数与奇数间，偶数与偶数间发生矛盾。

从而想到要保证分出后的奇数数组和偶数数组也要分别为相应的答案(漂亮数组)。因此使用递归的方法可以解决该问题。

例如对于 N = 5, 则要得到 N = 3 和 N = 2 的漂亮数组, 分别为 {1, 3, 2} 和 {1, 2}, 奇数部分乘以二减去一，偶数部分直接乘以二，即可得到 {1, 5, 3, 2, 4}，构造完成。

针对递归过程还可以做些优化，没有写。

时间复杂度

$O(N ^ 2)$

源代码

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
class Solution {
public:
    vector<int> beautifulArray(int N) {
        vector<int>ans;
        if (N == 0)
            return {};
        if (N == 1) {
            ans.push_back(1);
            return ans;
        }
        if (N == 2) {
            ans.push_back(1);
            ans.push_back(2);
            return ans;
        }
        int mid = (N + 1) / 2;
        vector<int>lef,rig;
        lef = beautifulArray(mid);
        rig = beautifulArray(N - mid);
        for (int i = 0; i < mid; i++)
            ans.push_back(lef[i] * 2 - 1);
        for (int i = 0; i < N - mid; i++)
            ans.push_back(rig[i] * 2);
        return ans;
    }
};
0%