【反证法】932. 漂亮数组
本文涉及知识点
分治 数学 反证法
LeetCode932. 漂亮数组
如果长度为 n 的数组 nums 满足下述条件，则认为该数组是一个 漂亮数组 ：
nums 是由范围 [1, n] 的整数组成的一个排列。
对于每个 0 <= i < j < n ，均不存在下标 k（i < k < j）使得 2 * nums[k] == nums[i] + nums[j] 。
给你整数 n ，返回长度为 n 的任一 漂亮数组 。本题保证对于给定的 n 至少存在一个有效答案。
示例 1 ：
输入：n = 4
输出：[2,1,4,3]
示例 2 ：
输入：n = 5
输出：[3,1,2,5,4]
提示：
1 <= n <= 1000
反证法
性质一：漂亮数组A各元素乘以m(m > 0 )形成的数组B是漂亮数组。用反证法证明：
假定存在2B[k] = B[i]+B[j]，则2B[k]/m = B[i]/m + B[j]/m。即A也不是漂亮数组，与假设矛盾。
性质二：漂亮数组A各元素加上m形成数组B，也是漂亮数组。证明类似性质一。
性质三：漂亮数组Ａ删除若干元素，仍然是漂亮数组。可用反证法证明。
性质四：漂亮数组A全部是奇数，漂亮数组B全部是偶数。则A+B 也是漂亮数组。如：A = {1,3} B = {2,4},则{1,3,2,4}也是漂亮数组。下面分类讨论：
{ A 是漂亮数组 i , j ∈ A B 是漂亮数组 i , j ∈ B n u m s [ i ] + n u m s [ j ] 是奇数， 2 × n u m s [ k ] 是偶数，两者不会相等。 i ∈ A , j ∈ B \begin{cases} A是漂亮数组 && i,j\in A \\ B是漂亮数组 && i,j \in B \\ nums[i]+nums[j]是奇数，2 \times nums[k]是偶数，两者不会相等。 && i \in A,j \in B \\ \end{cases} ⎩ ⎨ ⎧A是漂亮数组B是漂亮数组nums[i]+nums[j]是奇数，2×nums[k]是偶数，两者不会相等。i,j∈Ai,j∈Bi∈A,j∈B
思路
n = 1 arr1 = {1}
n = 2 arr2 = (arr1 × \times × 2-1)+(arr1 × \times × 2)
n=4 arr4 = (arr2 × \times × 2-1)+(arr2 × \times × 2)
⋯ \cdots ⋯
如果n 不是2的m次幂，则抛弃大于n的数。
代码
class Solution {
public:vector<int> beautifulArray(int n) {vector<int> pre = { 1 }; while (pre.size() < n) {vector<int> dp;auto Add = [&](int val) {if (val > n) { return; }dp.emplace_back(val);};for (int i = 0; i < pre.size(); i++) {Add(pre[i] * 2 - 1);}for (int i = 0; i < pre.size(); i++) {Add(pre[i] * 2 );}pre.swap(dp);}return pre;}
};
扩展阅读
视频课程
先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关推荐
| 我想对大家说的话 |
|---|
| 《喜缺全书算法册》以原理、正确性证明、总结为主。 |
| 按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。 |
| 有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注 |
| 闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
