一、题目大意
标签: 分治
https://leetcode.cn/problems/beautiful-array
对于某些固定的 N,如果数组 A 是整数 1, 2, ..., N 组成的排列,使得:
对于每个 i < j,都不存在 k 满足 i < k < j 使得 A[k] * 2 = A[i] + A[j]。
那么数组 A 是漂亮数组。
给定 N,返回任意漂亮数组 A(保证存在一个)。
示例 1:
输入:4
输出:[2,1,4,3]
示例 2:
输入:5
输出:[3,1,2,5,4]
提示:
1 <= N <= 1000
二、解题思路
题解参考:https://www.cnblogs.com/grandyang/p/12287146.html
分治法,按奇偶来分的话,因为奇数加偶数等于奇数,就不会是任何一个数字的2倍了。这就是奇偶分堆的好处,这时任意两个数字肯定不能分别从奇偶堆里取了,那可能你会问,奇数堆会不会有三个奇数打破这个规则呢?只要这个奇数堆是从一个漂亮数组按固定的规则变化而来的,就能保证一定也是漂亮数组,因为对于任意一个漂亮数组,若对每个数字都加上一个相同的数字,或者都乘上一个相同的数字,则一定还是漂亮数组,因为数字的之间的内在关系并没有改变。明白了上面这些,基本就可以解题了,假设此时已经有了一个长度为n的漂亮数组,如何将其扩大呢?可以将其中每个数字都乘以2并加1,就都会变成奇数,并且这个奇数数组还是漂亮的,然后再将每个数字都乘以2,那么都会变成偶数,并且这个偶数数组还是漂亮的,两个数组拼接起来,就会得到一个长度为 2n 的漂亮数组。就是这种思路,可以从1开始,1本身就是一个漂亮数组,然后将其扩大,注意这里要卡一个N,不能让扩大的数组长度超过N,只要在变为奇数和偶数时加个判定就行了,将不大于N的数组加入到新的数组中三、解题方法
3.1 Java实现
public class Solution { public int[] beautifulArray(int n) { List
ans = new ArrayList<>(); ans.add(1); while (ans.size() < n) { List t = new ArrayList<>(); for (int num : ans) { if (num * 2 - 1 <= n) { t.add(num * 2 - 1); } } for (int num : ans) { if (num * 2 <= n) { t.add(num * 2); } } ans = t; } return ans.stream() .mapToInt(Integer::intValue) .toArray(); } } 四、总结小记
- 2022/7/9 洗衣服涤不干会有味