【反证法】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}也是漂亮数组。下面分类讨论：
$$\{\begin{array}{llc}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{array}$$

思路

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++**实现。

原文地址：https://blog.csdn.net/he_zhidan/article/details/139912031

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！